# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
198062 | 2020-01-24T15:08:12 Z | dndhk | Editor (BOI15_edi) | C++14 | 127 ms | 12284 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]; int frt[MAX_N+1]; priority_queue<int> pq1, pq2; vector<int> vc; 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; } frt[i-1] = N+1; } for(int i=N-1; i>=0; i--){ if(vt[i].first==2 && prv[i]==-1){ v.pb({i, vt[i].second}); vc.pb(i); 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 = frt[j]; } else { vc.pb(j); v.pb({j, vt[j].second}); } } }else{ prv[v.back().first] = j; v.pop_back(); } if(v.empty()) break; } frt[vc.back()] = prv[vc.back()]; for(int j=vc.size()-2; j>=0; j--){ if(vc[j+1]==prv[vc[j]]-1){ frt[vc[j]] = frt[vc[j+1]]; }else{ frt[vc[j]] = prv[vc[j]]; } } while(!vc.empty()) vc.pop_back(); } } 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Incorrect | 3 ms | 612 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 11728 KB | Output is correct |
2 | Correct | 105 ms | 11172 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 6116 KB | Output is correct |
2 | Correct | 61 ms | 7244 KB | Output is correct |
3 | Correct | 66 ms | 8216 KB | Output is correct |
4 | Correct | 106 ms | 11596 KB | Output is correct |
5 | Correct | 127 ms | 12284 KB | Output is correct |
6 | Correct | 65 ms | 8812 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Incorrect | 3 ms | 612 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |