oj.uz

답안 #588930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588930 2022-07-04T07:53:26 Z radal The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 93 ms 32400 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];
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];
        cnt[A[i]]++;
        cnt[B[i]]++;
        ve[A[i]].pb(B[i]);
        ve[B[i]].pb(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) 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];
    rep(i,dd+1,ind+1){
        pll p = {h[ve[x][i]],ve[x][i]};
        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];
    rep(i,dd+1,ind+1){
        pll p = {h[ve[y][i]],ve[y][i]};
        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);
    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);
        else break;
    }
    return ans;
}

Subtask #1
0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14544 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 32284 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 32400 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 15856 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14416 KB Incorrect
2 Halted 0 ms 0 KB -