直接写的二分,调炸了,有没有人二分 A 了,给我个代码参考下呗Orz
#include<bits/stdc++.h>
using namespace std;
int n,m,Q,ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> m >> Q;
int mapp[n + 10][m + 10];
memset(mapp,0,sizeof(mapp));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
mapp[i][j] = 1;
}
}
for(int i = 1;i <= Q;i++){
int x,y;
cin >> x >> y;
if(mapp[x][y] == 1)mapp[x][y] = 0;
else if(mapp[x][y] == 0){
int up = INT_MIN,down = INT_MAX,left = INT_MIN,right = INT_MAX;
int l = 0 - 1,r = x + 1;
//cout << l << " " << r << "\n";
while(l + 1 < r){
int mid = (l + r) / 2;
if(mapp[mid][y] == 1){
up = max(up,mid);
l = mid;
}
else r = mid;
}
l = x,r = n + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mapp[mid][y] == 1){
down = min(down,mid);
r = mid;
}
else l = mid;
}
//cout << up << " " << down << "\n";
l = 1 - 1,r = y;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mapp[x][mid] == 1){
left = max(left,mid);
l = mid;
}
else r = mid;
}
l = y,r = m + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mapp[x][mid] == 1){
right = min(right,mid);
r = mid;
}
else l = mid;
}
//cout << x << " " << y << "\n";
// cout << mapp[3][2] << "\n";
//cout << up << " " << down << " " << left << " " << right << "\n";
if(up != INT_MIN){
mapp[up][y] = 0;
}
if(left != INT_MIN){
mapp[x][left] = 0;
}
if(down != INT_MAX){
mapp[down][y] = 0;
}
if(right != INT_MAX){
mapp[x][right] = 0;
}
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(mapp[i][j] == 1)ans ++;
}
}
cout << ans;
return 0;
}