Submission #1317581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317581		chaitanyamehta	Towers (NOI22_towers)	C++20	100 / 100	819 ms	162416 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e6+5;
vector<int> x(maxn) , y(maxn);

bool cmp(int a , int b){
    return x[a] < x[b];
}



signed main(){
    int n;cin>>n;

    for(int i = 0 ; i < n; i++)cin>>x[i]>>y[i];

    vector<vector<int>> p_by_rows(maxn);

    for(int i = 0 ;i < n ; i++){
        p_by_rows[y[i]].push_back(i);
    }
    for(int i = 0 ; i < maxn ; i++){
        sort(p_by_rows[i].begin() , p_by_rows[i].end() , cmp);
    }

    vector<int> pos(n);

    for(int i = 0 ; i < maxn ; i++){
        for(int j = 0 ;j < p_by_rows[i].size() ; j++){
            pos[p_by_rows[i][j]] = j;
        }
    }

    vector<bool> picked(n);
    vector<vector<int>> rowpick(maxn);


    for(int i = 0 ; i < maxn ; i++){
        if(p_by_rows[i].empty())continue;

        int a = p_by_rows[i].front();
        int b = p_by_rows[i].back();

        picked[a] = true;
        rowpick[i].push_back(a);

        if(a!= b){
            picked[b] = 1;
            rowpick[i].push_back(b);
        }
    }
    vector<int> colbot(maxn) , coltop(maxn) , colcnt(maxn);
    vector<vector<int>> waiting(maxn);

    for(int i = 0 ; i <n ; i++){
        if(!picked[i])continue;
        int c = x[i];

        if(colcnt[c] == 0){
            coltop[c] = colbot[c] = i;
            colcnt[c]++;
        }
        else if(colcnt[c] == 1){
            int j = coltop[c];
            if(y[i] < y[j]){
                colbot[c] = i;
                coltop[c] = j;
            }
            else{
                colbot[c] = j;
                coltop[c] =i;
            }
            colcnt[c]++;
        }
        else{
            if(y[i] < y[colbot[c]]){
                waiting[c].push_back(colbot[c]);
                colbot[c] = i;
            }
            else if(y[i] > y[coltop[c]]){
                waiting[c].push_back(coltop[c]);
                coltop[c] = i;
            }
            else{
                waiting[c].push_back(i);
            }
            colcnt[c]++;
        }
    }

    queue<int> q;
    vector<bool> inq(maxn , false);

    for(int i = 0 ; i < maxn ; i++){
        if(colcnt[i] > 2){
            q.push(i);
            inq[i] = 1;
        }
    }

    auto remove = [&](int y , int p){
        auto &v = rowpick[y];
        for(int i = 0 ; i < v.size() ; i++){
            if(v[i] == p){
                v[i]= v.back();
                v.pop_back();
                return;
            }
        }
    };

    while(!q.empty()){
        int c = q.front();q.pop();

        inq[c] = false;

        if(colcnt[c] <= 2)continue;
        if(waiting[c].empty())continue;
        int p = waiting[c].back();
        waiting[c].pop_back();

        if(!picked[p])continue;
        int Y = y[p];

        if(rowpick[Y].size() ==1){
            remove(Y , p);
            picked[p] = 0;
            colcnt[c]--;
            if(colcnt[c] >2&& !inq[c]){
                q.push(c);
                inq[c] = 1;
            }
            continue;
        }

        int a=rowpick[Y][0];
        int b = rowpick[Y][1];

        int left = (pos[a] < pos[b] ? a : b);
        int right = (a==left?b:a);

        int np;
        if(p == left){
            np=p_by_rows[Y][pos[p] + 1];
        }
        else{
            np = p_by_rows[Y][pos[p] - 1];
        }

        remove(Y , p);
        picked[p] = 0;
        colcnt[c]--;

        if(!picked[np]){
            picked[np] = 1;
            rowpick[Y].push_back(np);

            int c = x[np];

            if(colcnt[c] == 0){
                coltop[c] = colbot[c] = np;
                colcnt[c]++;
            }
            else if(colcnt[c] == 1){
                int j = coltop[c];
                if(y[np] < y[j]){
                    colbot[c] = np;
                    coltop[c] = j;
                }
                else{
                    colbot[c] = j;
                    coltop[c] =np;
                }
                colcnt[c]++;
            }
            else{
                if(y[np] < y[colbot[c]]){
                    waiting[c].push_back(colbot[c]);
                    colbot[c] = np;
                }
                else if(y[np] > y[coltop[c]]){
                    waiting[c].push_back(coltop[c]);
                    coltop[c] = np;
                }
                else{
                    waiting[c].push_back(np);
                }
                colcnt[c]++;
            }

            if(colcnt[c] > 2 && !inq[c]){
                inq[c] = 1;
                q.push(c);
            }
        }
        if(colcnt[c] > 2 && !inq[c]){
            inq[c] = 1;
            q.push(c);
        }
    }
    for(int i = 0 ; i < n ; i++){
        cout<<picked[i];
    }
}

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