Submission #498035

#	Time	Username	Problem	Language	Result	Execution time	Memory
498035		andrei_boaca	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2706 ms	53336 KiB

potion

#include <bits/stdc++.h>
#pragma GCC opimize("O3")
using namespace std;
typedef pair<int,int> pii;
const int C=40;
int n,d,u,q,h[100005],p1[200005],p2[200005];
unordered_set<int> setik[100005];
vector<int> vals[100005];
vector< pair< int, vector<int> > > checkpoint[100005];
vector<int> ck[100005];
vector<int> v;
vector<int> v1;
vector<int> rez;
vector<int> V1,V2,t;
bool isthere[100005];
pii day[200005];
int findpoz(int poz,int who)
{
    if(day[poz].first==who)
        return p1[poz];
    else
        return p2[poz];
}
void buildv(int x,int zi,int index)
{
    rez.clear();
    v1.clear();
    int st=0;
    int dr=checkpoint[x].size();
    int pozmax=-1;
    dr--;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(checkpoint[x][mij].first<=zi)
        {
            pozmax=max(pozmax,mij);
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    t.clear();
    if(pozmax!=-1)
    {
        for(int i=0;i<checkpoint[x][pozmax].second.size();i++)
        {
            int p=checkpoint[x][pozmax].second[i];
            v1.push_back(p);
            isthere[p]=1;
        }
        int poz=findpoz(checkpoint[x][pozmax].first,x);
        int nrit=0;
        for(int i=poz+1;i<vals[x].size()&&vals[x][i]<=zi;i++)
        {
            nrit++;
            int z=vals[x][i];
            int nod=(x^day[z].first^day[z].second);
            t.push_back(nod);
            if(isthere[nod]==0)
                isthere[nod]=1;
            else
                isthere[nod]=0;
        }
    }
    if(!t.empty())
    {
        for(int j=0;j<t.size();j++)
            v1.push_back(t[j]);
    }
    if(v1.empty())
    {
        if(index==1)
            V1=rez;
        else
            V2=rez;
        return;
    }
    for(int i=0;i<v1.size();i++)
        if(isthere[v1[i]]==1)
        {
            rez.push_back(h[v1[i]]);
            isthere[v1[i]]=0;
        }
    sort(rez.begin(),rez.end());
    if(index==1)
        V1=rez;
    else
        V2=rez;
}
void init(int N,int D, int H[])
{
    n=N;
    d=D;
    for(int i=0;i<n;i++)
        h[i]=H[i];
}
void curseChanges(int U, int A[], int B[])
{
    u=U;
    for(int i=1;i<=u;i++)
    {
        int a,b;
        a=A[i-1];
        b=B[i-1];
        day[i]={a,b};
        vals[a].push_back(i);
        p1[i]=vals[a].size();
        p1[i]--;
        vals[b].push_back(i);
        p2[i]=vals[b].size();
        p2[i]--;
        if(setik[a].find(b)!=setik[a].end())
        {
            setik[a].erase(b);
            setik[b].erase(a);
        }
        else
        {
            setik[a].insert(b);
            setik[b].insert(a);
        }
        if((int)vals[a].size()%C==1)
        {
            vector<int> aux;
            for(int j:setik[a])
                aux.push_back(j);
            checkpoint[a].push_back({i,aux});
        }
        if((int)vals[b].size()%C==1)
        {
            vector<int> aux;
            for(int j:setik[b])
                aux.push_back(j);
            checkpoint[b].push_back({i,aux});
        }
    }
}
int question(int x,int y,int zi)
{
    V1.clear();
    V2.clear();
    buildv(x,zi,1);
    buildv(y,zi,2);
    if(V1.empty()||V2.empty())
    {
        return 1000000000;
    }
    int ans=1e9;
    int j=0;
    for(int i=0;i<V1.size();i++)
    {
        j=max(j,0);
        while(j<V2.size()&&V2[j]<=V1[i])
            j++;
        j--;
        if(j>=0)
            ans=min(ans,abs(V1[i]-V2[j]));
        if(j+1<V2.size())
            ans=min(ans,abs(V1[i]-V2[j+1]));
    }
    return ans;
}

Compilation message (stderr)

potion.cpp:2: warning: ignoring '#pragma GCC opimize' [-Wunknown-pragmas]
    2 | #pragma GCC opimize("O3")
      | 
potion.cpp: In function 'void buildv(int, int, int)':
potion.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=0;i<checkpoint[x][pozmax].second.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=poz+1;i<vals[x].size()&&vals[x][i]<=zi;i++)
      |                         ~^~~~~~~~~~~~~~~
potion.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j=0;j<t.size();j++)
      |                     ~^~~~~~~~~
potion.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<v1.size();i++)
      |                 ~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:151:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i=0;i<V1.size();i++)
      |                 ~^~~~~~~~~~
potion.cpp:154:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         while(j<V2.size()&&V2[j]<=V1[i])
      |               ~^~~~~~~~~~
potion.cpp:159:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         if(j+1<V2.size())
      |            ~~~^~~~~~~~~~

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