Submission #1200184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200184		12345678	The Potion of Great Power (CEOI20_potion)	C++20	35 / 100	2631 ms	98736 KiB

potion

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, k=50;

int n, m;
vector<int> h;
vector<set<int>> sv[nx];
vector<pair<int, int>> event[nx];

void init(int N, int D, int H[]) {
    n=N;
    for (int i=0; i<n; i++) h.push_back(H[i]);
    for (int i=0; i<n; i++) event[i].push_back({0, 0}), sv[i].push_back(set<int> {});
}

void recalculate(int idx)
{
    auto tmp=sv[idx].back();
    for (int j=event[idx].size()-k+1; j<event[idx].size(); j++)
    {
        if (tmp.find(event[idx][j].second)!=tmp.end()) tmp.erase(event[idx][j].second);
        else tmp.insert(event[idx][j].second);
    }
    sv[idx].push_back(tmp);
}

vector<int> getstate(int idx, int date)
{
    int t=lower_bound(event[idx].begin(), event[idx].end(), make_pair(date, INT_MAX))-event[idx].begin()-1;
    int lst=(t+1)/k*k;
    auto tmp=sv[idx][(t+1)/k];
    for (int j=lst+1; j<=t; j++)
    {
        if (j==0) continue;
        if (tmp.find(event[idx][j].second)!=tmp.end()) tmp.erase(event[idx][j].second);
        else tmp.insert(event[idx][j].second);
    }
    vector<int> ch;
    for (auto x:tmp) ch.push_back(h[x]); //cout<<"query "<<idx<<' '<<x<<'\n';
    sort(ch.begin(), ch.end());
    return ch;
}

void curseChanges(int U, int A[], int B[]) {
    m=U;
    for (int i=0; i<m; i++)
    {
        event[A[i]].push_back({i+1, B[i]});
        if (event[A[i]].size()%k==0) recalculate(A[i]);
        event[B[i]].push_back({i+1, A[i]});
        if (event[B[i]].size()%k==0) recalculate(B[i]);
    }
}

int question(int x, int y, int d) {
    int res=1e9, idxy=0;
    auto hx=getstate(x, d), hy=getstate(y, d);
    if (hx.empty()||hy.empty()) return res;
    for (int i=0; i<hx.size(); i++)
    {
        while (idxy+1<hy.size()&&hy[idxy+1]<=hx[i]) idxy++;
        if (idxy<hy.size()) res=min(res, abs(hx[i]-hy[idxy]));
        if (idxy+1<hy.size()) res=min(res, abs(hx[i]-hy[idxy+1]));
    }
    return res;
}

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