Submission #872101

#	Time	Username	Problem	Language	Result	Execution time	Memory
872101		Trisanu_Das	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2185 ms	96468 KiB

potion

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,set<pii>> piv;
 
int n,h[100005];
const int sq=50;
vector<pii> c[100005];
vector<piv> v[100005];
 
bool comp(int a, int b) {return h[a]<h[b];}
 
void init(int N, int D, int H[]) {
    n=N;
    for (int i=0; i<n; ++i) h[i]=H[i], v[i].push_back(piv(0,{}));
}
 
void curseChanges(int U, int A[], int B[]) {
    for (int i=0; i<U; ++i) {
        c[A[i]].push_back(pii(i+1,B[i]));
        c[B[i]].push_back(pii(i+1,A[i]));
    }
 
    for (int i=0; i<n; ++i) {
        set<pii> temp;
        for (int j=0; j<c[i].size(); ++j) {
            int add=c[i][j].second;
            if (temp.find(pii(h[add],add))==temp.end()) temp.insert(pii(h[add],add));
            else temp.erase(temp.find(pii(h[add],add)));
            if ((j+1)%sq==0) v[i].push_back(piv(c[i][j].first,temp));
        }
    }
}
 
int question(int x, int y, int day) {
    int hx=upper_bound(v[x].begin(),v[x].end(),piv(day+1,{}))-v[x].begin()-1;
    int hy=upper_bound(v[y].begin(),v[y].end(),piv(day+1,{}))-v[y].begin()-1;
 
    set<pii> tempX=v[x][hx].second, tempY=v[y][hy].second;
 
    int Hx=upper_bound(c[x].begin(),c[x].end(),pii(v[x][hx].first,INT_MAX))-c[x].begin();
    int Hy=upper_bound(c[y].begin(),c[y].end(),pii(v[y][hy].first,INT_MAX))-c[y].begin();
 
    while (Hx<c[x].size() && c[x][Hx].first<=day) {
        int add=c[x][Hx].second;
        if (tempX.find(pii(h[add],add))==tempX.end()) tempX.insert(pii(h[add],add));
        else tempX.erase(tempX.find(pii(h[add],add)));
        ++Hx;
    }
 
    while (Hy<c[y].size() && c[y][Hy].first<=day) {
        int add=c[y][Hy].second;
        if (tempY.find(pii(h[add],add))==tempY.end()) tempY.insert(pii(h[add],add));
        else tempY.erase(tempY.find(pii(h[add],add)));
        ++Hy;
    }
 
    int ans=1e9;
    auto itx=tempX.begin(), ity=tempY.begin();
    while (itx!=tempX.end() && ity!=tempY.end()) {
        ans=min(ans,abs((*itx).first-(*ity).first));
        if ((*itx).first<(*ity).first) ++itx;
        else ++ity;
    }
    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int j=0; j<c[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while (Hx<c[x].size() && c[x][Hx].first<=day) {
      |            ~~^~~~~~~~~~~~
potion.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (Hy<c[y].size() && c[y][Hy].first<=day) {
      |            ~~^~~~~~~~~~~~

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