제출 #1148180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148180		imarn	Towers (NOI22_towers)	C++20	5 / 100	2101 ms	161924 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;
map<int,vector<pii>>mp;
map<int,int>fs,ls;
map<int,pii>dp,dp2;
bool vis[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.find(x)==mp.end())pq.push(x);
        mp[x].pb({y,i});
        fs[x]=0;ls[x]=(int)mp[x].size()-1;
    }
    for(auto it : mp){
        sort(mp[it.f].begin(),mp[it.f].end());
    }
    while(!pq.empty()){
        int x=pq.top();pq.pop();
        pii l=mp[x][fs[x]];
        pii r=mp[x][ls[x]];
        if(fs[x]<=ls[x]){
            if(dp.find(l.f)==dp.end())vis[l.s]=1,dp[l.f]={l.s,x};
            else if(dp2.find(l.f)==dp2.end())vis[l.s]=1,dp2[l.f]={l.s,x};
            else {
                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]--;
                pq.push(rs.s);
            }
        }
        if(fs[x]<ls[x]){
            if(dp.find(r.f)==dp.end())vis[r.s]=1,dp[r.f]={r.s,x};
            else if(dp2.find(r.f)==dp2.end())vis[r.s]=1,dp2[r.f]={r.s,x};
            else {
                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]--;
                pq.push(rs.s);
            }
        }
    }for(int i=1;i<=n;i++)cout<<vis[i];
}

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