Submission #866114

#	Time	Username	Problem	Language	Result	Execution time	Memory
866114		vnm06	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2294 ms	150140 KiB

potion

#include<bits/stdc++.h>
using namespace std;
 
int n, h[1000005];
 
void init(int N, int D, int H[]) 
{
    n=N;
    for(int i=0; i<n; i++) h[i]=H[i];
}
 
map<pair<int, int>, int> globalmp;
 
vector<pair<int, int> > st[2000000];
 
void update(int v, int le, int ri, int be, int en, int st1, int st2)
{
    if(le>en || ri<be) return;
    if(be<=le && ri<=en)
    {
        st[v].push_back({st1, st2});
        st[v].push_back({st2, st1});
        return;
    }
    int mid=(le+ri)/2;
    update(2*v, le, mid, be, en, st1, st2);
    update(2*v+1, mid+1, ri, be, en, st1, st2);
}
 
void curseChanges(int U, int A[], int B[]) 
{
    for(int i=0; i<U; i++)
    {
        if(A[i]>B[i]) swap(A[i], B[i]);
        map<pair<int, int>, int>::iterator it=globalmp.find({A[i], B[i]});
        if(it!=globalmp.end())
        {
            update(1, 0, 2e5+1, (*it).second, i, A[i], B[i]);
            globalmp.erase(it);
        }
        else
        {
            globalmp[{A[i], B[i]}]=i+1;
        }
    }
    map<pair<int, int>, int>::iterator it=globalmp.begin();
    while(it!=globalmp.end())
    {
        update(1, 0, 2e5+1, (*it).second, U, (*it).first.first, (*it).first.second);
        it++;
    }
    for(int i=0; i<2000000; i++) sort(st[i].begin(), st[i].end());
}
 
vector<int> vect[2];
 
void query(int v, int le, int ri, int day, int ch, int id)
{
    while(1)
    {
        int nle=-1, nri=st[v].size();
        while(nri-nle>1)
        {
            int mid=(nle+nri)/2;
            if(st[v][mid].first<ch) nle=mid;
            else nri=mid;
        }
        while(nri<st[v].size() && st[v][nri].first==ch)
        {
            vect[id].push_back(st[v][nri].second);
            nri++;
        }
        if(le==ri) return;
        int mid=(le+ri)/2;
        if(day<=mid)
        {
            v=2*v;
            ri=mid;
        }
        else
        {
            v=2*v+1;
            le=mid+1;

        }
    }
}
 
int question(int x, int y, int v) 
{
    vect[0].resize(0);
    vect[1].resize(0);
    query(1, 0, 2e5+1, v, x, 0);
    query(1, 0, 2e5+1, v, y, 1);
    int s1=vect[0].size(), s2=vect[1].size(), id1=0, id2=0;
    for(int i=0; i<s1; i++) vect[0][i]=h[vect[0][i]];
    for(int i=0; i<s2; i++) vect[1][i]=h[vect[1][i]];
    sort(vect[0].begin(), vect[0].end());
    sort(vect[1].begin(), vect[1].end());
    int tekd=1e9;
    while(id1<s1 && id2<s2)
    {
        int dist=vect[0][id1]-vect[1][id2];
        if(dist<0)
        {
            id1++;
            dist=-dist;
            if(dist<tekd) tekd=dist;
        }
        else
        {
            id2++;
            if(dist<tekd) tekd=dist;
        }
    }
    return tekd;
}

Compilation message (stderr)

potion.cpp: In function 'void query(int, int, int, int, int, int)':
potion.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(nri<st[v].size() && st[v][nri].first==ch)
      |               ~~~^~~~~~~~~~~~~

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