求 abc D
  • 板块灌水区
  • 楼主XYzero
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/9/7 22:16
  • 上次更新2024/9/8 10:38:47
查看原帖
求 abc D
917025
XYzero楼主2024/9/7 22:16

直接写的二分,调炸了,有没有人二分 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;
}
2024/9/7 22:16
加载中...