oj.uz

답안 #589138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589138 2022-07-04T09:38:47 Z radal The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2907 ms 172480 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 = 30;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19080 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19208 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 45 ms 32776 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 44952 KB Output is correct
2 Correct 309 ms 44976 KB Output is correct
3 Correct 430 ms 46356 KB Output is correct
4 Correct 1721 ms 106056 KB Output is correct
5 Correct 596 ms 43684 KB Output is correct
6 Correct 2907 ms 154916 KB Output is correct
7 Correct 806 ms 54320 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 44908 KB Output is correct
2 Correct 2194 ms 167536 KB Output is correct
3 Correct 1368 ms 98552 KB Output is correct
4 Correct 2269 ms 154184 KB Output is correct
5 Correct 466 ms 51388 KB Output is correct
6 Correct 2350 ms 154312 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 21092 KB Output is correct
2 Correct 172 ms 21200 KB Output is correct
3 Correct 276 ms 21200 KB Output is correct
4 Correct 849 ms 23124 KB Output is correct
5 Correct 803 ms 22608 KB Output is correct
6 Correct 177 ms 19804 KB Output is correct
7 Correct 774 ms 22736 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19080 KB Output is correct
2 Correct 12 ms 19208 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 11 ms 19280 KB Output is correct
5 Correct 45 ms 32776 KB Output is correct
6 Correct 300 ms 44952 KB Output is correct
7 Correct 309 ms 44976 KB Output is correct
8 Correct 430 ms 46356 KB Output is correct
9 Correct 1721 ms 106056 KB Output is correct
10 Correct 596 ms 43684 KB Output is correct
11 Correct 2907 ms 154916 KB Output is correct
12 Correct 806 ms 54320 KB Output is correct
13 Correct 264 ms 44908 KB Output is correct
14 Correct 2194 ms 167536 KB Output is correct
15 Correct 1368 ms 98552 KB Output is correct
16 Correct 2269 ms 154184 KB Output is correct
17 Correct 466 ms 51388 KB Output is correct
18 Correct 2350 ms 154312 KB Output is correct
19 Correct 57 ms 21092 KB Output is correct
20 Correct 172 ms 21200 KB Output is correct
21 Correct 276 ms 21200 KB Output is correct
22 Correct 849 ms 23124 KB Output is correct
23 Correct 803 ms 22608 KB Output is correct
24 Correct 177 ms 19804 KB Output is correct
25 Correct 774 ms 22736 KB Output is correct
26 Correct 965 ms 80584 KB Output is correct
27 Correct 1385 ms 98780 KB Output is correct
28 Correct 1436 ms 89964 KB Output is correct
29 Correct 1389 ms 105948 KB Output is correct
30 Correct 2585 ms 154400 KB Output is correct
31 Correct 2361 ms 172480 KB Output is correct
32 Correct 2334 ms 154584 KB Output is correct