oj.uz

Submission #888363

# Submission time Handle Problem Language Result Execution time Memory
888363 2023-12-17T05:11:19 Z 1075508020060209tc Alternating Current (BOI18_alternating) C++14
0 / 100
 45 ms 10836 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 1 ms 8540 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 1 ms 8540 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 1 ms 8540 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10664 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 21 ms 10680 KB Output is correct
4 Correct 22 ms 10588 KB Output is correct
5 Incorrect 45 ms 10836 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 1 ms 8540 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -