oj.uz

Submission #588948

# Submission time Handle Problem Language Result Execution time Memory
588948 2022-07-04T08:08:06 Z radal The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 54816 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 = 300;
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 j = ind/sq;
    int dd = j*sq;
    st1 = st[x][dd];
    ind = lower_bound(all(wh[x]),make_pair(dd,0))-wh[x].begin();
    int sz = wh[x].size();
    rep(i,ind+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;
    j = ind/sq;
    dd = j*sq;
    st2 = st[y][dd];
    ind = lower_bound(all(wh[y]),make_pair(dd,0))-wh[y].begin();
    sz = wh[y].size();
    rep(i,ind+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 9 ms 19024 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19408 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 12 ms 19280 KB Output is correct
4 Correct 46 ms 32888 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 44892 KB Output is correct
2 Correct 292 ms 44944 KB Output is correct
3 Execution timed out 3087 ms 40124 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 44896 KB Output is correct
2 Execution timed out 3102 ms 54816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 21072 KB Output is correct
2 Correct 290 ms 20936 KB Output is correct
3 Execution timed out 3076 ms 20992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Correct 11 ms 19408 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 12 ms 19280 KB Output is correct
5 Correct 46 ms 32888 KB Output is correct
6 Correct 279 ms 44892 KB Output is correct
7 Correct 292 ms 44944 KB Output is correct
8 Execution timed out 3087 ms 40124 KB Time limit exceeded
9 Halted 0 ms 0 KB -