제출 #1200238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200238		12345678	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	126 ms	24412 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;
    if (t+1!=event[idx].size()) cout<<1/0;
    int lst=(t)/k*k;
    auto tmp=sv[idx][(t)/k];
    for (int j=lst+1; j<=t; j++)
    {
        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==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);
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

potion.cpp: In function 'std::vector<int> getstate(int, int)':
potion.cpp:32:40: warning: division by zero [-Wdiv-by-zero]
   32 |     if (t+1!=event[idx].size()) cout<<1/0;
      |                                       ~^~

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