# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198044 | 2020-01-24T14:48:24 Z | dndhk | Editor (BOI15_edi) | C++14 | 3000 ms | 9912 KB |
#include <bits/stdc++.h> #define pb push_back using namespace std; const int MAX_N = 300000; typedef pair<int, int> pii; vector<pii> vt; int prv[MAX_N+1]; int N; vector<pii> v; int num[MAX_N+1]; int chk[MAX_N+1]; priority_queue<int> pq1, pq2; int main(){ scanf("%d", &N); for(int i=1; i<=N; i++){ int x; scanf("%d", &x); if(x>0){ vt.pb({1, x}); }else{ vt.pb({2, -x}); prv[i-1] = -1; } } for(int i=N-1; i>=0; i--){ if(vt[i].first==2 && prv[i]==-1){ v.pb({i, vt[i].second}); for(int j=i-1; j>=0; j--){ if(vt[j].first==2){ if(v.back().second>vt[j].second){ prv[v.back().first] = j; v.pop_back(); }else{ if(prv[j]!=-1){ j = prv[j]; } else v.pb({j, vt[j].second}); } }else{ prv[v.back().first] = j; v.pop_back(); } if(v.empty()) break; } } } for(int i=0; i<N; i++){ if(vt[i].first==1){ num[i] = i; pq1.push(num[i]); chk[i] = true; }else{ //cout<<"*"<<prv[i]<<endl; num[i] = num[prv[i]]; chk[num[i]] = (!chk[num[i]]); if(chk[num[i]]){ pq1.push(num[i]); }else{ pq2.push(num[i]); } } while(!pq1.empty() && !pq2.empty() && pq1.top()==pq2.top()){ pq1.pop(); pq2.pop(); } if(pq1.empty()){ printf("0\n"); } else printf("%d\n", vt[pq1.top()].second); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 4 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 11 ms | 476 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 4 ms | 632 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 4 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 9912 KB | Output is correct |
2 | Correct | 102 ms | 9720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 5368 KB | Output is correct |
2 | Correct | 60 ms | 6252 KB | Output is correct |
3 | Execution timed out | 3006 ms | 4936 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 4 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 11 ms | 476 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 4 ms | 632 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 4 ms | 632 KB | Output is correct |
10 | Correct | 102 ms | 9912 KB | Output is correct |
11 | Correct | 102 ms | 9720 KB | Output is correct |
12 | Correct | 51 ms | 5368 KB | Output is correct |
13 | Correct | 60 ms | 6252 KB | Output is correct |
14 | Execution timed out | 3006 ms | 4936 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |