Submission #1148310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148310		imarn	Towers (NOI22_towers)	C++20	100 / 100	451 ms	76764 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=1e6+5;
vector<pii>mp[mxn];
int fs[mxn],ls[mxn];
pii dp[mxn],dp2[mxn];
bool vis[mxn]{0};
bool done[mxn]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;priority_queue<int>pq;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        if(mp[x].size()==0)pq.push(x);
        mp[x].pb({y,i});
        fs[x]=0;ls[x]=(int)mp[x].size()-1;
        dp[y]=dp2[y]={-1,-1};
    }
    for(int i=1;i<mxn;i++){
        sort(mp[i].begin(),mp[i].end());
    }
    while(!pq.empty()){
        int x=pq.top();pq.pop();
        if(done[x])continue;bool ch=0;
        pii l=mp[x][fs[x]];
        pii r=mp[x][ls[x]];
        if(fs[x]>ls[x])continue;
        if(fs[x]<=ls[x]&&!vis[l.s]){
            if(dp[l.f].f==-1)vis[l.s]=1,dp[l.f]={l.s,x};
            else if(dp2[l.f].f==-1){
                vis[l.s]=1,dp2[l.f]={l.s,x};
                if(dp2[l.f].s>dp[l.f].s)swap(dp[l.f],dp2[l.f]);
            }
            else {
                if(x<dp2[l.f].s){
                    pii rs=dp2[l.f];vis[rs.f]=0;dp2[l.f]={l.s,x};vis[l.s]=1;
                    if(mp[rs.s][fs[rs.s]].f==l.f)fs[rs.s]++;
                    else if(mp[rs.s][ls[rs.s]].f==l.f)ls[rs.s]--;
                    done[rs.s]=0;pq.push(rs.s);
                }
                else if(x>dp[l.f].s){
                    pii rs=dp[l.f];vis[rs.f]=0;dp[l.f]={l.s,x};vis[l.s]=1;
                    if(mp[rs.s][fs[rs.s]].f==l.f)fs[rs.s]++;
                    else if(mp[rs.s][ls[rs.s]].f==l.f)ls[rs.s]--;
                    done[rs.s]=0;pq.push(rs.s);
                }
                else{
                    fs[x]++;ch=1;
                }
            }
        }
        if(fs[x]<ls[x]&&!vis[r.s]){
            if(dp[r.f].f==-1)vis[r.s]=1,dp[r.f]={r.s,x};
            else if(dp2[r.f].f==-1){
                vis[r.s]=1,dp2[r.f]={r.s,x};
                if(dp2[r.f].s>dp[r.f].s)swap(dp[r.f],dp2[r.f]);
            }
            else {
                if(x<dp2[r.f].s){
                    pii rs=dp2[r.f];vis[rs.f]=0;dp2[r.f]={r.s,x};vis[r.s]=1;
                    if(mp[rs.s][fs[rs.s]].f==r.f)fs[rs.s]++;
                    else if(mp[rs.s][ls[rs.s]].f==r.f)ls[rs.s]--;
                    done[rs.s]=0;pq.push(rs.s);
                }
                else if(x>dp[r.f].s){
                    pii rs=dp[r.f];vis[rs.f]=0;dp[r.f]={r.s,x};vis[r.s]=1;
                    if(mp[rs.s][fs[rs.s]].f==r.f)fs[rs.s]++;
                    else if(mp[rs.s][ls[rs.s]].f==r.f)ls[rs.s]--;
                    done[rs.s]=0;pq.push(rs.s);
                }
                else {
                    ls[x]--;ch=1;
                }
            }
        }if(!ch)done[x]=1;
        else pq.push(x);
    }
    for(int i=1;i<=n;i++)cout<<vis[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