# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198077 | 2020-01-24T15:55:29 Z | dndhk | Editor (BOI15_edi) | C++14 | 262 ms | 60380 KB |
#include <bits/stdc++.h> #define pb push_back using namespace std; const int MAX_N = 300000; const int MAX_K = 20; 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; vector<int> vc; int cnt[MAX_N+1]; pii frt[MAX_N+1][MAX_K+1]; void make_prv(){ for(int i=0; i<N; i++){ if(vt[i].first==1){ for(int j=0; j<MAX_K; j++){ frt[i][j] = {i, 0}; } }else{ int n = i; for(int j=MAX_K-1; j>=0; j--){ //cout<<n<<" "<<j<<" "<<frt[n-1][j].second<<" "<<vt[i].second<<endl; if(frt[n-1][j].second>=vt[i].second){ n = frt[n-1][j].first; } } prv[i] = n-1; //cout<<i<<" "<<prv[i]<<endl; frt[i][0] = {prv[i], vt[i].second}; //cout<<frt[i][0].first<<" "<<frt[i][0].second<<endl; for(int j=1; j<MAX_K; j++){ if(frt[i][j-1].first==0){ frt[i][j] = {0, 0}; }else{ frt[i][j].first = frt[frt[i][j-1].first-1][j-1].first; frt[i][j].second = min(frt[i][j-1].second, frt[frt[i][j-1].first-1][j-1].second); } //cout<<frt[i][j].first<<" "<<frt[i][j].second<<endl; } } } } 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; } } make_prv(); 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 | 376 KB | Output is correct |
2 | Correct | 0 ms | 1272 KB | Output is correct |
3 | Correct | 2 ms | 520 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 1400 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 5 ms | 1400 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 1372 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 167 ms | 57764 KB | Output is correct |
2 | Correct | 156 ms | 59100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 80 ms | 28956 KB | Output is correct |
2 | Correct | 96 ms | 35844 KB | Output is correct |
3 | Correct | 210 ms | 45692 KB | Output is correct |
4 | Correct | 157 ms | 59152 KB | Output is correct |
5 | Correct | 172 ms | 60124 KB | Output is correct |
6 | Correct | 185 ms | 57020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 0 ms | 1272 KB | Output is correct |
3 | Correct | 2 ms | 520 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 1400 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 5 ms | 1400 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 1372 KB | Output is correct |
10 | Correct | 167 ms | 57764 KB | Output is correct |
11 | Correct | 156 ms | 59100 KB | Output is correct |
12 | Correct | 80 ms | 28956 KB | Output is correct |
13 | Correct | 96 ms | 35844 KB | Output is correct |
14 | Correct | 210 ms | 45692 KB | Output is correct |
15 | Correct | 157 ms | 59152 KB | Output is correct |
16 | Correct | 172 ms | 60124 KB | Output is correct |
17 | Correct | 185 ms | 57020 KB | Output is correct |
18 | Correct | 165 ms | 59968 KB | Output is correct |
19 | Correct | 163 ms | 59916 KB | Output is correct |
20 | Correct | 262 ms | 57052 KB | Output is correct |
21 | Correct | 156 ms | 59100 KB | Output is correct |
22 | Correct | 173 ms | 60380 KB | Output is correct |