Submission #1147450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147450		Pacybwoah	Towers (NOI22_towers)	C++20	100 / 100	465 ms	159792 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
typedef long long ll;
int inf = 1e9;
const int maxn = 1000005;
set<pair<int, int>> sx[maxn]; // (y, id)
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> pts(n), cur(maxn);
    for(int i = 0; i < n; i++) cin >> pts[i].first >> pts[i].second;
    string ans(n, '0');
    vector<vector<pair<int, int>>> allx(maxn);
    for(int i = 0; i < n; i++) allx[pts[i].second].emplace_back(pts[i].first, i);
    vector<int> left(n, -1), rht(n, -1);
    for(int i = 1; i < maxn; i++){
        if(!allx[i].empty()){
            sort(allx[i].begin(), allx[i].end());
            int sz = (int)allx[i].size();
            for(int j = 0; j < sz - 1; j++){
                rht[allx[i][j].second] = allx[i][j + 1].second;
                left[allx[i][j + 1].second] = allx[i][j].second;
            }
            cur[i] = make_pair(allx[i][0].first, allx[i][sz - 1].first);
            sx[cur[i].first].emplace(i, allx[i][0].second);
            if(sz > 1) sx[cur[i].second].emplace(i, allx[i][sz - 1].second);
        }
    }
    queue<int> q;
    for(int i = 1; i < maxn; i++){
        if((int)sx[i].size() > 2) q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        //cout << x << "\n";
        q.pop();
        int sz = (int)sx[x].size();
        if(sz <= 2) continue;
        auto iter = next(sx[x].begin());
        int nxt;
        for(int i = 1; i < sz - 1; i++){
            auto [y, id] = (*iter);
            iter = next(iter);
            if(cur[y].first == x){
                nxt = rht[id];
                if(nxt == -1) continue;
                cur[y].first = pts[nxt].first;
                sx[cur[y].first].emplace(y, nxt);
                if((int)sx[cur[y].first].size() > 2) q.push(cur[y].first);
            }
            else{
                nxt = left[id];
                if(nxt == -1) continue;
                cur[y].second = pts[nxt].first;
                sx[cur[y].second].emplace(y, nxt);
                if((int)sx[cur[y].second].size() > 2) q.push(cur[y].second);
            }
        }
        while(sz > 2){
            sz--;
            sx[x].erase(next(sx[x].begin()));
        }
    }
    for(int x = 1; x < maxn; x++){
        for(auto &[y, id]: sx[x]){
            ans[id] = '1';
        }
    }
    cout << ans << "\n";
}
// g++ -std=c++20 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pC.cpp

• 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