oj.uz

Submission #588970

# Submission time Handle Problem Language Result Execution time Memory
588970 2022-07-04T08:20:05 Z radal The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2952 ms 107356 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 1e9+7,inf = 1e9+10,sq = 60;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int n,d,h[N],a[N],b[N],u,cnt[N];
vector<set<pll> > st[N];
set<pll> st1,st2;
vector<int> ti[N],v1,ve[N];
vector<pll> wh[N];
void init(int N, int D, int H[]) {
    n = N;
    d = D;
    rep(i,0,n) h[i] = H[i];
}
 
void curseChanges(int U, int A[], int B[]) {
    u = U;
    rep(i,0,n){
        st[i].resize(1);
        ti[i].pb(0);
        wh[i].pb({0,0});
    }
    rep(i,0,U){
        a[i+1] = A[i];
        b[i+1] = B[i];
        cnt[A[i]]++;
        cnt[B[i]]++;
        ve[A[i]].pb(B[i]);
        ve[B[i]].pb(A[i]);
        wh[A[i]].pb({i+1,B[i]});
        wh[B[i]].pb({i+1,A[i]});
        if (cnt[A[i]] == sq){
            cnt[A[i]] = 0;
            int sz = st[A[i]].size();
            st[A[i]].pb(st[A[i]].back());
            ti[A[i]].pb(i+1);
            for (int u : ve[A[i]]){
                if (st[A[i]][sz].find({h[u],u}) != st[A[i]][sz].end())
                    st[A[i]][sz].erase({h[u],u});
                else
                    st[A[i]][sz].insert({h[u],u});
            }
            ve[A[i]].clear();
        }
        if (cnt[B[i]] == sq){
            cnt[B[i]] = 0;
            int sz = st[B[i]].size();
            st[B[i]].pb(st[B[i]].back());
            ti[B[i]].pb(i+1);
            for (int u : ve[B[i]]){
                if (st[B[i]][sz].find({h[u],u}) != st[B[i]][sz].end())
                    st[B[i]][sz].erase({h[u],u});
                else
                    st[B[i]][sz].insert({h[u],u});
            }
            ve[B[i]].clear();
        }
    }
}
 
int question(int x, int y, int v) {
    if (!v || ti[x].empty() || ti[y].empty()) return 1000000000;
    st1.clear();
    st2.clear();
    int ind = upper_bound(all(ti[x]),v)-ti[x].begin()-1;
    int dd = ind*sq;
    st1 = st[x][ind];
    int sz = wh[x].size();
    rep(i,dd+1,sz){
        if (wh[x][i].X > v) break;
        pll p = {h[wh[x][i].Y],wh[x][i].Y};
        if (st1.find(p) != st1.end())
            st1.erase(p);
        else
            st1.insert(p);
    }
    ind = upper_bound(all(ti[y]),v)-ti[y].begin()-1;
    dd = ind*sq;
    st2 = st[y][ind];
    sz = wh[y].size();
    rep(i,dd+1,sz){
        if (wh[y][i].X > v) break;
        pll p = {h[wh[y][i].Y],wh[y][i].Y};
        if (st2.find(p) != st2.end())
            st2.erase(p);
        else
            st2.insert(p);
    }
    if (st1.empty() || st2.empty()) return 1000000000;
    v1.clear();
    int po = 0,ans = 1000000000;
    for (pll x : st1)
        v1.pb(x.X);
    sz = v1.size();
    for (pll x : st2){
        while(po < sz && v1[po] <= x.X) po++;
        if (po) ans = min(ans,x.X-v1[po-1]); 
        if (po < sz) ans = min(ans,v1[po]-x.X);
        else break;
    }
    return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19044 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19280 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 11 ms 19300 KB Output is correct
4 Correct 39 ms 32840 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 44976 KB Output is correct
2 Correct 326 ms 44960 KB Output is correct
3 Correct 500 ms 42820 KB Output is correct
4 Correct 1825 ms 65924 KB Output is correct
5 Correct 673 ms 31676 KB Output is correct
6 Correct 2952 ms 98620 KB Output is correct
7 Correct 879 ms 48768 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 44904 KB Output is correct
2 Correct 2269 ms 104848 KB Output is correct
3 Correct 1495 ms 70404 KB Output is correct
4 Correct 2378 ms 98304 KB Output is correct
5 Correct 448 ms 48072 KB Output is correct
6 Correct 2581 ms 98504 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 21072 KB Output is correct
2 Correct 235 ms 20944 KB Output is correct
3 Correct 425 ms 21072 KB Output is correct
4 Correct 1057 ms 21972 KB Output is correct
5 Correct 959 ms 21840 KB Output is correct
6 Correct 182 ms 19724 KB Output is correct
7 Correct 987 ms 21828 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19044 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 11 ms 19300 KB Output is correct
5 Correct 39 ms 32840 KB Output is correct
6 Correct 298 ms 44976 KB Output is correct
7 Correct 326 ms 44960 KB Output is correct
8 Correct 500 ms 42820 KB Output is correct
9 Correct 1825 ms 65924 KB Output is correct
10 Correct 673 ms 31676 KB Output is correct
11 Correct 2952 ms 98620 KB Output is correct
12 Correct 879 ms 48768 KB Output is correct
13 Correct 264 ms 44904 KB Output is correct
14 Correct 2269 ms 104848 KB Output is correct
15 Correct 1495 ms 70404 KB Output is correct
16 Correct 2378 ms 98304 KB Output is correct
17 Correct 448 ms 48072 KB Output is correct
18 Correct 2581 ms 98504 KB Output is correct
19 Correct 49 ms 21072 KB Output is correct
20 Correct 235 ms 20944 KB Output is correct
21 Correct 425 ms 21072 KB Output is correct
22 Correct 1057 ms 21972 KB Output is correct
23 Correct 959 ms 21840 KB Output is correct
24 Correct 182 ms 19724 KB Output is correct
25 Correct 987 ms 21828 KB Output is correct
26 Correct 1138 ms 61516 KB Output is correct
27 Correct 1593 ms 70524 KB Output is correct
28 Correct 1651 ms 66976 KB Output is correct
29 Correct 1640 ms 65868 KB Output is correct
30 Correct 2838 ms 98284 KB Output is correct
31 Correct 2545 ms 107356 KB Output is correct
32 Correct 2597 ms 98460 KB Output is correct