Submission #138776

#TimeUsernameProblemLanguageResultExecution timeMemory
138776popovicirobertQueue (CEOI06_queue)C++14
86 / 100
1068 ms51060 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("Ofast") #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 /*const int MOD = (int) 1e9 + 7; inline int lgput(int a, int b) { int ans = 1; while(b > 0) { if(b & 1) ans = (1LL * ans * a) % MOD; b >>= 1; a = (1LL * a * a) % MOD; } return ans; } inline void mod(int &x) { if(x >= MOD) x -= MOD; } inline void add(int &x, int y) { x += y; mod(x); } inline void sub(int &x, int y) { x += MOD - y; mod(x); } inline void mul(int &x, int y) { x = (1LL * x * y) % MOD; }*/ /*int fact[], invfact[]; inline void prec(int n) { fact[0] = 1; for(int i = 1; i <= n; i++) { fact[i] = (1LL * fact[i - 1] * i) % MOD; } invfact[n] = lgput(fact[n], MOD - 2); for(int i = n - 1; i >= 0; i--) { invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD; } } inline int comb(int n, int k) { if(n < k) return 0; return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD; }*/ using namespace std; const int INF = 1e9; map <int, int> prv, nxt; inline void fix(int a) { if(prv[a] == 0) { prv[a] = a - 1; } if(nxt[a] == 0) { nxt[a] = a + 1; } } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, q; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; for(i = 0; i < n; i++) { int a, b; cin >> a >> b; fix(a), fix(b); int x = prv[a], y = nxt[a]; fix(x), fix(y); nxt[x] = y; prv[y] = x; fix(prv[b]); nxt[prv[b]] = a; prv[a] = prv[b]; nxt[a] = b; prv[b] = a; } vector <int> all; for(auto it : nxt) { if(it.first > 0) all.push_back(it.first); } for(auto it : prv) { if(it.first > 0) all.push_back(it.first); } sort(all.begin(), all.end()); all.resize(unique(all.begin(), all.end()) - all.begin()); map <int, bool> vis; for(auto it : all) { vis[it] = 1; } vector < pair <int, int> > aux; for(auto it : all) { //cerr << it << " " << prv[it] << " " << nxt[it] << "\n"; if(vis[prv[it]] == 0) { aux.push_back({prv[it], it}); } } sort(aux.begin(), aux.end()); map <int, int> id, pos; // id[x] = cine se afla la x // pos[x] = la ce pos e x vector < pair <int, int> > len; vector <int> sp; int last = 1, sum = 0; for(auto it : aux) { len.push_back({last, prv[it.second]}); sum += prv[it.second] - last + 1; sp.push_back(sum); int cur = it.second; while(vis[cur]) { sum++; pos[cur] = sum, id[sum] = cur; cur = nxt[cur]; } last = cur; } len.push_back({last, INF}); sum += INF - last + 1; sp.push_back(sum); cin >> q; while(q--) { char ch; int x; cin >> ch >> x; if(ch == 'P') { if(pos[x] != 0) { cout << pos[x] << "\n"; continue; } int p = upper_bound(len.begin(), len.end(), make_pair(x, INF)) - len.begin() - 1; cout << sp[p] - (len[p].second - x) << "\n"; } else { if(id[x] != 0) { cout << id[x] << "\n"; continue; } int p = lower_bound(sp.begin(), sp.end(), x) - sp.begin(); cout << len[p].second - (sp[p] - x) << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...