제출 #931767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931767		sysia	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2360 ms	81152 KiB

potion

#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo2 = 1e9;
int n, d;
vector<int>h;
vector<T>edges, life;

void init(int _n, int _d, int H[]){
    n = _n; d = _d;
    h.resize(n);
    for (int i = 0; i<n; i++) h[i] = H[i];
}

int sz = 1;
vector<vector<T>>tab;

void init(int s){
    while (sz < s) sz*=2;
    tab.resize(2*sz);
}

void update(int x, int lx, int rx, int i){
    if (lx > life[i].second || rx < life[i].first) return;
    if (lx >= life[i].first && rx <= life[i].second) {
        for (int rep = 0; rep < 2; rep++){
            tab[x].emplace_back(edges[i]);
            swap(edges[i].first, edges[i].second);
        }
        return;
    }
    int m = (lx+rx)/2;
    update(2*x, lx, m, i);
    update(2*x+1, m+1, rx, i);
}

void curseChanges(int u, int A[], int B[]){
    map<T, int>alive;
    for (int i = 0; i<u; i++){
        if (A[i] > B[i]) swap(A[i], B[i]);
        if (alive.find({A[i], B[i]}) == alive.end()){
            alive[{A[i], B[i]}] = i+1;
        } else {
            edges.emplace_back(A[i], B[i]);
            life.emplace_back(alive[{A[i], B[i]}], i);
            alive.erase({A[i], B[i]});
        }
    }
    for (auto [v, i]: alive){
        edges.emplace_back(v);
        life.emplace_back(i, u);
    }
    init(u+1);
    debug(edges);
    debug(life);
    for (int i = 0; i<(int)life.size(); i++){
        update(1, 0, sz-1, i);
    }
    for (int i = 1; i<2*sz; i++){
        sort(tab[i].begin(), tab[i].end());
    }
}


void find(int x, int lx, int rx, int pos, int v, vector<T>&curr){
    //z wierzcholka x
    int L = (int)(lower_bound(tab[x].begin(), tab[x].end(), T{v, 0}) - tab[x].begin());
    for (int rep = L; rep < (int)tab[x].size(); rep++){
        if (tab[x][rep].first != v) break;
        curr.emplace_back(h[tab[x][rep].second], v);
    }
    if (lx == rx) return;
    int m = (lx+rx)/2;
    if (pos <= m) find(2*x, lx, m, pos, v, curr);
    else find(2*x+1, m+1, rx, pos, v, curr);
};


int question(int x, int y, int v){
    vector<T>X;
    find(1, 0, sz-1, v, x, X);
    find(1, 0, sz-1, v, y, X);
    debug(X);
    sort(X.begin(), X.end());
    
    int ans = oo2;
    for (int i = 1; i<(int)X.size(); i++){
        if (X[i].second != X[i-1].second) {
            ans = min(ans, X[i].first-X[i-1].first);
        }
    }
    return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30