Submission #1185635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185635		SalihSahin	Towers (NOI22_towers)	C++20	12 / 100	2087 ms	195012 KiB

Main

#include "bits/stdc++.h"
#define pb push_back
#define int long long
using namespace std;

const int inf = 1e16;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    set<int> xset, yset;
    vector<array<int, 2> > a(n);
    vector<pair<int, int> > inp(n);
    for(int i = 0; i < n; i++){
        cin>>a[i][0]>>a[i][1];
        inp[i] = {a[i][0], a[i][1]};
        xset.insert(a[i][0]);
        yset.insert(a[i][1]);
    }
    sort(a.begin(), a.end());

    map<int, int> cnty;
    vector<pair<int, int> > ans;
    map<int, int> comp;
    int ind = 0;
    for(auto itr: yset){
        comp[itr] = ind++;
    }
    vector<int> bucket[yset.size()];
    for(int i = 0; i < n; i++){
        bucket[comp[a[i][1]]].pb(a[i][0]);
    }
    for(int i = 0; i < yset.size(); i++){
        sort(bucket[i].begin(), bucket[i].end());
    }


    int l = 0, r = n-1;
    while(xset.size() > 1){
        auto u = *xset.begin();
        auto d = *xset.rbegin();

        map<int, int> cntval;

        vector<int> up, dp;
        while(a[l][0] == u){
            up.pb(a[l][1]);
            cntval[a[l][1]] += 1;
            l++;
        }
        while(a[r][0] == d){
            dp.pb(a[r][1]);
            cntval[a[r][1]] += 2;
            r--;
        }
        reverse(dp.begin(), dp.end());

        int lu = 0, ru = up.size()-1;
        int ld = 0, rd = dp.size()-1;

        while(lu < up.size()){
            if(cnty[up[lu]] == 3){
                lu++;
                continue;
            }

            if(cnty[up[lu]] == 1){
                int buckind = comp[up[lu]];
                auto nxt = lower_bound(bucket[buckind].begin(), bucket[buckind].end(), u + 1) - bucket[buckind].begin();
                if(nxt < bucket[buckind].size() && bucket[buckind][nxt] <= d){
                    lu++;
                    continue;
                }
            }

            break;
        }

        while(ru >= 0){
            if(cnty[up[ru]] == 3){
                ru--;
                continue;
            }

            if(cnty[up[ru]] == 1){
                int buckind = comp[up[ru]];
                auto nxt = lower_bound(bucket[buckind].begin(), bucket[buckind].end(), u + 1) - bucket[buckind].begin();
                if(nxt < bucket[buckind].size() && bucket[buckind][nxt] <= d){
                    ru--;
                    continue;
                }
            }

            break;
        }

        while(ld < dp.size()){
            if(cnty[dp[ld]] == 3){
                ld++;
                continue;
            }

            if(cnty[dp[ld]] == 2){
                int buckind = comp[dp[ld]];
                auto nxt = lower_bound(bucket[buckind].begin(), bucket[buckind].end(), u) - bucket[buckind].begin();
                if(nxt < bucket[buckind].size() && bucket[buckind][nxt] < d){
                    ld++;
                    continue;
                }
            }

            break;
        }

        while(rd >= 0){
            if(cnty[dp[rd]] == 3){
                rd--;
                continue;
            }

            if(cnty[dp[rd]] == 2){
                int buckind = comp[dp[rd]];
                auto nxt = lower_bound(bucket[buckind].begin(), bucket[buckind].end(), u) - bucket[buckind].begin();
                if(nxt < bucket[buckind].size() && bucket[buckind][nxt] < d){
                    rd--;
                    continue;
                }
            }

            break;
        }

        /*
        cout<<u<<" değeri için -> "<<lu<<" "<<ru<<endl;
        for(auto itr: up) cout<<itr<<" ";
        cout<<endl;
        cout<<d<<" değeri için -> "<<ld<<" "<<rd<<endl;
        for(auto itr: dp) cout<<itr<<" ";
        cout<<endl;
        */

        if(lu < up.size()) ans.pb({u, up[lu]});
        if(ru >= 0 && ru != lu) ans.pb({u, up[ru]});
        if(ld < dp.size()) ans.pb({d, dp[ld]});
        if(rd >= 0 && rd != ld) ans.pb({d, dp[rd]});

        if(lu < up.size()) cnty[up[lu]] += 1;
        if(ru >= 0 && ru != lu) cnty[up[ru]] += 1;
        if(ld < dp.size()) cnty[dp[ld]] += 2;
        if(rd >= 0 && rd != ld) cnty[dp[rd]] += 2;

        xset.erase(xset.find(u));
        xset.erase(xset.find(d));
    }

    if(xset.size()){
        auto i = *xset.begin();
        vector<int> p;
        while(l < a.size() && a[l][0] == i){
            p.pb(a[l][1]);
            l++;
        }

        int lp = 0, rp = p.size()-1;
        while(lp < p.size() && cnty[p[lp]] == 3) lp++;
        while(rp >= 0 && cnty[p[rp]] == 3) rp--;

        if(lp < p.size()) ans.pb({i, p[lp]});
        if(rp >= 0 && rp != lp) ans.pb({i, p[rp]});
    }

    sort(ans.begin(), ans.end());
    /*
    cout<<endl;
    for(auto itr: ans){
        cout<<itr.first<<" "<<itr.second<<endl;
    }
    cout<<endl;
    */

    string res = "";
    for(int i = 0; i < n; i++){
        auto k = lower_bound(ans.begin(), ans.end(), inp[i]) - ans.begin();
        if(k < ans.size() && ans[k] == inp[i]) res += '1';
        else res += '0';
    }

    cout<<res<<endl;
    return 0;
}

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