Submission #1131711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131711		lighton	Towers (NOI22_towers)	C++20	23 / 100	2100 ms	205460 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(), v.end()
#define forf(i, s, e) for (int i = s; i <= e; i++)
#define forb(i, s, e) for (int i = s; i >= e; i--)
#define idx(i, v) (lower_bound(all(v), i) - v.begin())
#define comp(v) v.erase(unique(all(v)), v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
int X[1000001],Y[1000001];
set<pair<int,int> > xpos[1000001],ypos[1000001];
int ans[1000001];

bool chk(int i){
    int flg = 0;
    if(next(xpos[X[i]].find({Y[i],i})) == xpos[X[i]].end()) flg |= 1;
    if(xpos[X[i]].find({Y[i],i}) == xpos[X[i]].begin()) flg |= 1;
    if(next(ypos[Y[i]].find({X[i],i})) == ypos[Y[i]].end()) flg |= 2;
    if(ypos[Y[i]].find({X[i],i}) == ypos[Y[i]].begin()) flg |= 2;
    return (flg == 3);
}
void ers(int i, vector<int> &q){
    auto xit = xpos[X[i]].lower_bound({Y[i],i});
    auto yit = ypos[Y[i]].lower_bound({X[i],i});
    if(xit != xpos[X[i]].end()){
        int j = xit->se;
        if(chk(j) && ans[j] == -1) q.pb(j),ans[j] = 1;
    }
    if(xit != xpos[X[i]].begin()){
        int j = prev(xit)->se;
        if(chk(j) && ans[j] == -1) q.pb(j),ans[j] = 1;
    }
    if(yit != ypos[Y[i]].end()){
        int j = yit->se;
        if(chk(j) && ans[j] == -1) q.pb(j),ans[j] = 1;
    }
    if(yit != ypos[Y[i]].begin()){
        int j = prev(yit)->se;
        if(chk(j) && ans[j] == -1) q.pb(j),ans[j] = 1;
    }
}
int main() {
    IO
    cin>>N;
    //N = 88;
    forf(i,1,N) {
        cin >> X[i] >> Y[i];
        /*int x = rand()%17+1;
        int y = rand()%17+1;
        while(xpos[x].lower_bound({y,0})->fs == y) x = rand()%17+1,y = rand()%17+1;
        X[i] = x, Y[i] = y;
        cout<<x<< " " << y<<"\n";*/
        xpos[X[i]].insert({Y[i], i}), ypos[Y[i]].insert({X[i], i});
    }
    vector<int> q;
    forf(i,1,N) ans[i] = -1;
    forf(i,1,N) if(chk(i)) q.pb(i),ans[i] = 1;

    while(q.size()) {
        vector<int> sx,sy;
        for(int &i : q){
            if(ans[xpos[X[i]].begin()->se] == 1 && ans[prev(xpos[X[i]].end())->se] == 1) sx.pb(X[i]);
            if(ans[ypos[Y[i]].begin()->se] == 1 && ans[prev(ypos[Y[i]].end())->se] == 1) sy.pb(Y[i]);
        }
        q.resize(0);

        sort(all(sx)), comp(sx), sort(all(sy)), comp(sy);
        vector<int> p;
        for(int &x : sx) for(auto &[_,i] : xpos[x]){
            if(ans[i] == -1) p.pb(i),ans[i] = 0;
        }
        for(int &y : sy) for(auto &[_,i] : ypos[y]){
            if(ans[i] == -1) p.pb(i),ans[i] = 0;
        }
        sort(all(p)), comp(p);
        for(int &i : p) xpos[X[i]].erase({Y[i],i}), ypos[Y[i]].erase({X[i],i});
        for(int &i : p) ers(i,q);
    }

    forf(i,1,N){
        
        cout<<ans[i];
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19