Submission #104942

#TimeUsernameProblemLanguageResultExecution timeMemory
104942ShtefOGLEDALA (COI15_ogledala)C++14
19 / 100
216 ms15736 KiB
#include <iostream> #include <vector> #include <set> using namespace std; struct nes{ int l, r; friend bool operator <(nes x, nes y){ if(x.r - x.l + 1 == y.r - y.l + 1) return x.l < y.l; return x.r - x.l + 1 > y.r - y.l + 1; } }; int m, n, q, a[300005], c[300005]; multiset <nes> s; set <int> b; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> m >> n >> q; for(int i = 1 ; i <= n ; ++i){ cin >> a[i]; c[i] = a[i]; } if(a[1] != 1){ s.insert((nes){1, a[1] - 1}); } for(int i = 2 ; i <= n ; ++i){ if(a[i] != a[i - 1] + 1){ s.insert((nes){a[i - 1] + 1, a[i] - 1}); } } if(a[n] != m){ s.insert((nes){a[n] + 1, m}); } for(int i = n + 1 ; i <= min(m, 300000) ; ++i){ nes o = *s.begin(); s.erase(s.begin()); int mid = (o.l + o.r) / 2; c[i] = mid; if(mid > o.l){ s.insert((nes){o.l, mid - 1}); } if(o.r > mid){ s.insert((nes){mid + 1, o.r}); } } for(int i = 0 ; i < q ; ++i){ int x; cin >> x; cout << c[x] << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...