Submission #974850

#TimeUsernameProblemLanguageResultExecution timeMemory
974850CookieThe Potion of Great Power (CEOI20_potion)C++14
100 / 100
1139 ms37240 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair #define ull unsigned long long const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 19972207, pr = 31; const int mxn = 2e5 + 5, mxq = 1e5 + 5, sq = 105, mxv = 64; //const int base = (1 <<18); const ll inf = 1e9, neg = -69420, inf2 = 1e14; int n, D, u, q; vt<int>comp[mxn + 1]; vt<vt<int>>day[mxn + 1], height[mxn + 1]; int h[mxn + 1], qa[mxn + 1], qb[mxn + 1]; void find(vt<int>&v, vt<int>&he, int x){ int id = lower_bound(ALL(v), x) - v.begin(); int id2 = lower_bound(ALL(he), h[x]) - he.begin(); if(id == sz(v) || v[id] != x){ v.insert(v.begin() + id, x); he.insert(he.begin() + id2, h[x]); }else{ v.erase(v.begin() + id); he.erase(he.begin() + id2); } } int get(vt<int>&a, vt<int>&b){ //for(auto i: a)cout << i << " "; //cout << "\n"; //for(auto i: b)cout << i << " "; //cout << "\n"; if(sz(a) == 0 || sz(b) == 0)return(inf); int r = 0, ans = inf; for(int i = 0; i < sz(b); i++){ while(r < sz(a) && a[r] <= b[i]){ ans = min(ans, b[i] - a[r++]); } if(r != sz(a))ans = min(ans, a[r] - b[i]); } return(ans); } void lzupd(int a){ vt<int>nwd = day[a].back(), nwh = height[a].back(); for(int j = sz(comp[a]) - sq; j < sz(comp[a]); j++){ if(!j)continue; if(qa[comp[a][j]] == a){ find(nwd, nwh, qb[comp[a][j]]); }else if(qb[comp[a][j]] == a){ find(nwd, nwh, qa[comp[a][j]]); } } day[a].pb(nwd); height[a].pb(nwh); } vt<int>lzget(int x, int d){ int block = d / sq; vt<int>nwd = day[x][block], nwh = height[x][block]; for(int j = block * sq; j <= d; j++){ if(!j)continue; if(qa[comp[x][j]] == x){ find(nwd, nwh, qb[comp[x][j]]); }else if(qb[comp[x][j]] == x){ find(nwd, nwh, qa[comp[x][j]]); } } return(nwh); } void init(int N, int _D, int H[]) { n = N; D = _D; for(int i = 0; i < n; i++)h[i] = H[i]; } void curseChanges(int U, int A[], int B[]) { for(int i = 0; i < n; i++)comp[i].pb(0); vt<int>emp; for(int i = 0; i < n; i++){ day[i].pb(emp); height[i].pb(emp); } u = U; for(int i = 1; i <= u; i++){ int a, b; a = A[i - 1], b = B[i - 1]; qa[i] = a; qb[i] = b; comp[a].pb(i); comp[b].pb(i); if(sz(comp[a]) % sq == 0){ lzupd(a); }if(sz(comp[b]) % sq == 0){ lzupd(b); } } } int question(int x, int y, int v) { int id = upper_bound(ALL(comp[x]), v) - comp[x].begin() - 1; int id2 = upper_bound(ALL(comp[y]), v) - comp[y].begin() - 1; vt<int>hx = lzget(x, id), hy = lzget(y, id2); return(get(hx, hy)); } /* int main() { int N, D, U, Q; std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> N >> D >> U >> Q; int *F = new int[N]; for (int i=0; i<N; i++) std::cin >> F[i]; init(N, D, F); int *A = new int[U], *B = new int[U]; for (int i=0; i<U; i++) { std::cin >> A[i] >> B[i]; } curseChanges(U, A, B); bool correct = true; for (int i=0; i<Q; i++) { int X,Y,V,CorrectAnswer; std::cin >> X >> Y >> V >> CorrectAnswer; int YourAnswer = question(X,Y,V); if (YourAnswer != CorrectAnswer) { std::cout << "WA! Question: " << i << " (X=" << X << ", Y=" << Y << ", V=" << V << ") " << "Your answer: " << YourAnswer << " Correct Answer: " << CorrectAnswer << std::endl; correct = false; } else { std::cerr << YourAnswer << " - OK" << std::endl; } } if (correct) { std::cout << "Correct." << std::endl; } else std::cout << "Incorrect." << std::endl; return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...