# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
128292 | Osama_Alkhodairy | Minerals (JOI19_minerals) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//~ #include "minerals.h"
#include "grader.cpp"
using namespace std;
set <int> active;
vector <int> s, e;
int curl, curr;
int curq;
int query(int x){
if(active.count(x)) active.erase(x);
else active.insert(x);
return curq = Query(x);
}
void solve(int l, int r, vector <int> &cur){
if(r < l) return;
if(l == r){
assert(cur.size() == 1);
Answer(e[l], cur[0]);
return;
}
int mid = (l + r) / 2;
for(int i = l ; i <= mid ; i++){
if(active.count(e[i])) continue;
query(e[i]);
}
while(1){
auto it = active.upper_bound(e[mid]);
if(it == active.end() || *it > e[r]) break;
query(*it);
}
vector <int> left, right;
for(auto &i : cur){
int las = curq;
int x = query(i);
if(x == las) left.push_back(i);
else right.push_back(i);
query(i);
}
solve(l, mid, left);
solve(mid + 1, r, right);
}
void Solve(int N){
int prev = 0;
for(int i = 1 ; i <= 2 * N ; i++){
int cur = query(i);
if(cur != prev) s.push_back(i);
else e.push_back(i);
prev = cur;
}
for(auto &i : s) query(i);
curl = 0;
curr = N - 1;
solve(0, N - 1, s);
}