제출 #578173

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

potion

#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 2e5+7;
int n, d, h[N], u, a[N], b[N];
set <int> trusted[N/2];
bool subtask4 = 0;

void init(int N, int D, int H[]) {
    n = N; d = D;
    int flag = 0;
    for (int i = 0; i < N; i++) {
        h[i] = H[i];
        flag |= h[i];
    }
    if (flag < 2) {
        subtask4 = 1;
    }
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; i++) {
        a[i] = A[i]; b[i] = B[i];
        {
            auto last = sz(trusted[a[i]]);
            trusted[a[i]].insert(b[i]);
            if (sz(trusted[a[i]]) == last) 
                trusted[a[i]].erase(trusted[a[i]].find(b[i]));
        }
        {
            auto last = sz(trusted[b[i]]);
            trusted[b[i]].insert(a[i]);
            if (sz(trusted[b[i]]) == last) 
                trusted[b[i]].erase(trusted[b[i]].find(a[i]));
        }
    }
}

int question(int x, int y, int v) {
    vector <pii> friends;
    set <int> thief = trusted[x], evil_shaman = trusted[y];
    for (int i = u-1; i >= v; i--) {
        if (a[i] == x) {
            auto last = sz(thief);
            thief.insert(b[i]);
            if (sz(thief) == last) thief.erase(thief.find(b[i]));
        }
        else if (b[i] == x) {
            auto last = sz(thief);
            thief.insert(a[i]);
            if (sz(thief) == last) thief.erase(thief.find(a[i]));
        }
        if (a[i] == y) {
            auto last = sz(evil_shaman);
            evil_shaman.insert(b[i]);
            if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(b[i]));
        }
        else if (b[i] == y) {
            auto last = sz(evil_shaman);
            evil_shaman.insert(a[i]);
            if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(a[i]));
        }
    }
    set <int> tt, ss;
    for (auto to : thief) tt.insert(h[to]);
    for (auto to : evil_shaman) ss.insert(h[to]);
    
    vector <int> t, s;
    for (auto to : tt) t.pb(to);
    for (auto to : ss) s.pb(to);
    int mn = 1e9;
    int last = -1;
    for (auto to : s) {
        while (last + 1 < sz(t) && t[last+1] <= to) {
            last++;
        }
        if (last > -1) {
            mn = min(mn, abs(t[last]-to));
        }
    }
    reverse(all(t));
    reverse(all(s));
    last = -1;
    for (auto to : s) {
        while (last + 1 < sz(t) && t[last+1] >= to) {
            last++;
        }
        if (last > -1) {
            mn = min(mn, abs(t[last]-to));
        }
    }
    
    
    return mn;
}

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