# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
61939 | 2018-07-27T05:56:57 Z | koosaga(#1793) | popa (BOI18_popa) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "popa.h" using namespace std; typedef pair<int, int> pi; typedef long long lint; pi range(int v, int *l, int *r){ pi ret(v, v); if(l[v] != -1) ret.first = range(l[v], l, r).first; if(r[v] != -1) ret.second = range(r[v], l, r).second; return ret; } int solve(int N, int *l, int *r){ for(int i=0; i<N; i++) l[i] = r[i] = -1; int cur_root = 0; for(int i=1; i<N; i++){ vector<int> v; for(int j=cur_root; j!=-1; j=r[j]){ v.push_back(j); } while(v.size()){ auto l = range(v.back()); if(query(l.first, l.second + 1, v.back(), v.back()) == 1){ break; } else v.pop_back(); } if(v.empty()){ l[i] = cur_root; cur_root = i; } else{ r[v.back()] = i; } } }