oj.uz

Submission #588906

# Submission time Handle Problem Language Result Execution time Memory
588906 2022-07-04T07:27:17 Z radal The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 2950 ms 262144 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 = 500;
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;
vector<set<pll> > st[N];
set<pll> st1,st2;
vector<int> ti[N],v1;
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);
    }
    rep(i,0,U){
        a[i+1] = A[i];
        b[i+1] = B[i];
        if ((i+1)%sq == 0){
            int l = i-sq+1;
            rep(k,l,i+1){
                if (ti[A[k]].back() != i+1){
                    ti[A[k]].pb(i+1);
                    st[A[k]].pb(st[A[k]].back());
                }
                if (ti[B[k]].back() != i+1){
                    ti[B[k]].pb(i+1);
                    st[B[k]].pb(st[B[k]].back());
                }
                int sz1 = st[A[k]].size(),sz2 = st[B[k]].size();;
                if (st[A[k]][sz1-1].find({h[B[k]],B[k]}) != st[A[k]][sz1-1].end()){
                    st[A[k]][sz1-1].erase({h[B[k]],B[k]});
                    st[B[k]][sz2-1].erase({h[A[k]],A[k]});
                }
                else{
                    st[A[k]][sz1-1].insert({h[B[k]],B[k]});
                    st[B[k]][sz2-1].insert({h[A[k]],A[k]});
                }
            }
        }
    }
}
 
int question(int x, int y, int v) {
    if (!v) return 1000000000;
    int dd = 0;
    if (v >= sq){
        int j = v/sq;
        dd = j*sq;
        int ind = upper_bound(all(ti[x]),dd)-ti[x].begin()-1;
        st1 = st[x][ind];
        ind = upper_bound(all(ti[y]),dd)-ti[y].begin()-1;
        st2 = st[y][ind];
    }
    else{
        st1.clear();
        st2.clear();
    }
    rep(i,dd+1,v+1){
        if (a[i] == x){
            if (st1.find({h[b[i]],b[i]}) != st1.end())
                st1.erase({h[b[i]],b[i]});
            else
                st1.insert({h[b[i]],b[i]});
        }
        if (a[i] == y){
            if (st2.find({h[b[i]],b[i]}) != st2.end())
                st2.erase({h[b[i]],b[i]});
            else
                st2.insert({h[b[i]],b[i]});
        }
        if (b[i] == x){
            if (st1.find({h[a[i]],a[i]}) != st1.end())
                st1.erase({h[a[i]],a[i]});
            else
                st1.insert({h[a[i]],a[i]});
        }
        if (b[i] == y){
            if (st2.find({h[a[i]],a[i]}) != st2.end())
                st2.erase({h[a[i]],a[i]});
            else
                st2.insert({h[a[i]],a[i]});
        }
    }
    if (st1.empty() || st2.empty()) return 1000000000;
    v1.clear();
    int po = 0,ans = 1000000000;
    for (pll x : st1) v1.pb(x.X);
    int 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);
    }
    return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10064 KB Output is correct
2 Correct 6 ms 10064 KB Output is correct
3 Correct 7 ms 10064 KB Output is correct
4 Correct 29 ms 20124 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 109404 KB Output is correct
2 Correct 551 ms 109556 KB Output is correct
3 Correct 254 ms 43464 KB Output is correct
4 Runtime error 312 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 109456 KB Output is correct
2 Correct 2950 ms 73892 KB Output is correct
3 Runtime error 363 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 13952 KB Output is correct
2 Correct 144 ms 12012 KB Output is correct
3 Correct 984 ms 11344 KB Output is correct
4 Correct 821 ms 14776 KB Output is correct
5 Correct 835 ms 14872 KB Output is correct
6 Correct 144 ms 17232 KB Output is correct
7 Correct 1307 ms 12368 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 7 ms 10064 KB Output is correct
3 Correct 6 ms 10064 KB Output is correct
4 Correct 7 ms 10064 KB Output is correct
5 Correct 29 ms 20124 KB Output is correct
6 Correct 543 ms 109404 KB Output is correct
7 Correct 551 ms 109556 KB Output is correct
8 Correct 254 ms 43464 KB Output is correct
9 Runtime error 312 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -