oj.uz

Submission #589151

# Submission time Handle Problem Language Result Execution time Memory
589151 2022-07-04T09:41:01 Z radal The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2760 ms 228172 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 = 21;
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 19124 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19212 KB Output is correct
2 Correct 12 ms 19280 KB Output is correct
3 Correct 15 ms 19280 KB Output is correct
4 Correct 43 ms 32848 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 44980 KB Output is correct
2 Correct 326 ms 44908 KB Output is correct
3 Correct 312 ms 48972 KB Output is correct
4 Correct 1649 ms 140524 KB Output is correct
5 Correct 571 ms 48456 KB Output is correct
6 Correct 2760 ms 203064 KB Output is correct
7 Correct 947 ms 59560 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 44876 KB Output is correct
2 Correct 2295 ms 221236 KB Output is correct
3 Correct 1352 ms 122668 KB Output is correct
4 Correct 2227 ms 201984 KB Output is correct
5 Correct 474 ms 54240 KB Output is correct
6 Correct 2448 ms 202580 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 21076 KB Output is correct
2 Correct 161 ms 21288 KB Output is correct
3 Correct 242 ms 21344 KB Output is correct
4 Correct 845 ms 24008 KB Output is correct
5 Correct 860 ms 23332 KB Output is correct
6 Correct 173 ms 20176 KB Output is correct
7 Correct 767 ms 23460 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19124 KB Output is correct
2 Correct 12 ms 19212 KB Output is correct
3 Correct 12 ms 19280 KB Output is correct
4 Correct 15 ms 19280 KB Output is correct
5 Correct 43 ms 32848 KB Output is correct
6 Correct 349 ms 44980 KB Output is correct
7 Correct 326 ms 44908 KB Output is correct
8 Correct 312 ms 48972 KB Output is correct
9 Correct 1649 ms 140524 KB Output is correct
10 Correct 571 ms 48456 KB Output is correct
11 Correct 2760 ms 203064 KB Output is correct
12 Correct 947 ms 59560 KB Output is correct
13 Correct 314 ms 44876 KB Output is correct
14 Correct 2295 ms 221236 KB Output is correct
15 Correct 1352 ms 122668 KB Output is correct
16 Correct 2227 ms 201984 KB Output is correct
17 Correct 474 ms 54240 KB Output is correct
18 Correct 2448 ms 202580 KB Output is correct
19 Correct 53 ms 21076 KB Output is correct
20 Correct 161 ms 21288 KB Output is correct
21 Correct 242 ms 21344 KB Output is correct
22 Correct 845 ms 24008 KB Output is correct
23 Correct 860 ms 23332 KB Output is correct
24 Correct 173 ms 20176 KB Output is correct
25 Correct 767 ms 23460 KB Output is correct
26 Correct 960 ms 96964 KB Output is correct
27 Correct 1456 ms 122980 KB Output is correct
28 Correct 1456 ms 109768 KB Output is correct
29 Correct 1448 ms 140632 KB Output is correct
30 Correct 2730 ms 202360 KB Output is correct
31 Correct 2436 ms 228172 KB Output is correct
32 Correct 2644 ms 202548 KB Output is correct