Submission #888363

#	Time	Username	Problem	Language	Result	Execution time	Memory
888363		1075508020060209tc	Alternating Current (BOI18_alternating)	C++14	0 / 100	45 ms	10836 KiB

alternating

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

int n;int m;
pair<pair<int,int>,int>ar[500005];
int freq[500005];
int freq2[500005];


int ans[500005];
int fans[500005];
void chk(){

for(int i=1;i<=m;i++){
    if(ans[i]){
        fans[ar[i].second]=1;
        freq[ar[i].first.first]++;
        freq[ar[i].first.second+1]--;
    }else{
        freq2[ar[i].first.first]++;
        freq2[ar[i].first.second+1]--;
    }
}


for(int i=1;i<=n;i++){
    freq[i]+=freq[i-1];
    freq2[i]+=freq2[i-1];
    if(freq[i]==0||freq2[i]==0){
        cout<<"impossible\n";exit(0);
    }
}

}


signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i].first.first;
    cin>>ar[i].first.second;
    ar[i].second=i;
}
sort(ar+1,ar+m+1);
int stx=0;int sty=0;int xrr=1;
priority_queue<pair<int,int>>pq;
for(int i=1;i<=m;i++){
    if(ar[i].first.first<=stx+1&&ar[i].first.second<=sty){
        stx=max(stx,ar[i].first.second);
        continue;
    }
    if(ar[i].first.second<=sty){continue;}
    if(ar[i].first.first>stx+1){
        ans[i]=1;
        sty=ar[i].first.second;
        continue;
    }
    pq.push({ar[i].first.second,i});
    if(pq.size()==2){
        int r1=pq.top().first;int id1=pq.top().second;
        int r2=pq.top().first;int id2=pq.top().second;
        if(r1>sty){
            sty=r1;
            stx=r2;
            ans[id1]=1;
        }else{
            stx=max(stx,r1);
            sty=max(sty,r2);
            ans[id2]=1;
        }
        pq.pop();
        pq.pop();
    }
}
chk();
for(int i=1;i<=m;i++){
    cout<<fans[i];
}



}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:46:25: warning: unused variable 'xrr' [-Wunused-variable]
   46 | int stx=0;int sty=0;int xrr=1;
      |                         ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26