Submission #866090

#	Time	Username	Problem	Language	Result	Execution time	Memory
866090		vnm06	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	42 ms	262144 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;

set<pair<int, int> > st[8000000];

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].insert({st1, st2});
        st[v].insert({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.insert({{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++;
    }
}

vector<int> vect[2];

void query(int v, int le, int ri, int day, int ch, int id)
{
    if(le<=day && day<=ri)
    {
        set<pair<int, int> >::iterator it=st[v].lower_bound({ch, -1});
        while(it!=st[v].end())
        {
            if((*it).first!=ch) break;
            vect[id].push_back((*it).second);
            it++;
        }
    }
    if(le==ri) return;
    int mid=(le+ri)/2;
    if(day<=mid) query(2*v, le, mid, day, ch, id);
    else query(2*v+1, mid+1, ri, day, ch, id);
}

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;
}

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