oj.uz

Submission #888362

# Submission time Handle Problem Language Result Execution time Memory
888362 2023-12-17T05:07:26 Z 1075508020060209tc Alternating Current (BOI18_alternating) C++14
0 / 100
 53 ms 11800 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,ar[i].second});
    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[i]=1;
        }else{
            stx=max(stx,r1);
            sty=max(sty,r2);
            ans[i]=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:61:35: warning: unused variable 'id1' [-Wunused-variable]
   61 |         int r1=pq.top().first;int id1=pq.top().second;
      |                                   ^~~
alternating.cpp:62:35: warning: unused variable 'id2' [-Wunused-variable]
   62 |         int r2=pq.top().first;int id2=pq.top().second;
      |                                   ^~~
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 40 ms 10676 KB Output is correct
2 Correct 2 ms 8696 KB Output is correct
3 Correct 24 ms 10924 KB Output is correct
4 Correct 24 ms 11272 KB Output is correct
5 Incorrect 53 ms 11800 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 -