oj.uz

답안 #589142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589142 2022-07-04T09:39:48 Z radal The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 3000 ms 230236 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 = 20;
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 19024 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 44980 KB Output is correct
2 Correct 307 ms 44872 KB Output is correct
3 Correct 320 ms 49392 KB Output is correct
4 Correct 1612 ms 146168 KB Output is correct
5 Correct 553 ms 50072 KB Output is correct
6 Execution timed out 3019 ms 211020 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 44896 KB Output is correct
2 Correct 2415 ms 230236 KB Output is correct
3 Correct 1536 ms 126720 KB Output is correct
4 Correct 2525 ms 210008 KB Output is correct
5 Correct 535 ms 54728 KB Output is correct
6 Correct 2795 ms 210476 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 21072 KB Output is correct
2 Correct 189 ms 21308 KB Output is correct
3 Correct 250 ms 21416 KB Output is correct
4 Correct 950 ms 24144 KB Output is correct
5 Correct 900 ms 23408 KB Output is correct
6 Correct 198 ms 20176 KB Output is correct
7 Correct 830 ms 23636 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19024 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 19208 KB Output is correct
5 Correct 43 ms 32824 KB Output is correct
6 Correct 310 ms 44980 KB Output is correct
7 Correct 307 ms 44872 KB Output is correct
8 Correct 320 ms 49392 KB Output is correct
9 Correct 1612 ms 146168 KB Output is correct
10 Correct 553 ms 50072 KB Output is correct
11 Execution timed out 3019 ms 211020 KB Time limit exceeded
12 Halted 0 ms 0 KB -