Submission #1215324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215324		lopkus	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	2546 ms	100176 KiB

potion

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
vector<int> h;
vector<set<pair<int, 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<pair<int, int>> {});
}

void recalculate(int idx)
{
    auto tmp=sv[idx].back();
    for (int j=event[idx].size()-k; j<event[idx].size(); j++)
    {
        if (tmp.find({h[event[idx][j].second], event[idx][j].second})!=tmp.end()) tmp.erase({h[event[idx][j].second], event[idx][j].second});
        else tmp.insert({h[event[idx][j].second], 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)/k*k;
    auto tmp=sv[idx][(t)/k];
    for (int j=lst+1; j<=t; j++)
    {
        if (tmp.find({h[event[idx][j].second], event[idx][j].second})!=tmp.end()) tmp.erase({h[event[idx][j].second], event[idx][j].second});
        else tmp.insert({h[event[idx][j].second], event[idx][j].second});
    }
    vector<int> ch;
    for (auto x:tmp) ch.push_back(x.first); //cout<<"query "<<idx<<' '<<x<<'\n';
    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==1) recalculate(A[i]);
        event[B[i]].push_back({i+1, A[i]});
        if (event[B[i]].size()%k==1) 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);
    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: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30