oj.uz

Submission #498035

# Submission time Handle Problem Language Result Execution time Memory
498035 2021-12-24T09:53:04 Z andrei_boaca The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2706 ms 53336 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12744 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13104 KB Output is correct
2 Correct 10 ms 13128 KB Output is correct
3 Correct 11 ms 13128 KB Output is correct
4 Correct 21 ms 14220 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 53072 KB Output is correct
2 Correct 407 ms 53212 KB Output is correct
3 Correct 170 ms 21104 KB Output is correct
4 Correct 1317 ms 33728 KB Output is correct
5 Correct 506 ms 39560 KB Output is correct
6 Correct 2706 ms 49880 KB Output is correct
7 Correct 616 ms 43708 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 53000 KB Output is correct
2 Correct 1176 ms 37216 KB Output is correct
3 Correct 968 ms 46348 KB Output is correct
4 Correct 1492 ms 49564 KB Output is correct
5 Correct 514 ms 53336 KB Output is correct
6 Correct 1619 ms 49640 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15644 KB Output is correct
2 Correct 92 ms 13472 KB Output is correct
3 Correct 133 ms 13344 KB Output is correct
4 Correct 726 ms 15148 KB Output is correct
5 Correct 744 ms 15524 KB Output is correct
6 Correct 105 ms 14108 KB Output is correct
7 Correct 600 ms 13696 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12744 KB Output is correct
2 Correct 10 ms 13104 KB Output is correct
3 Correct 10 ms 13128 KB Output is correct
4 Correct 11 ms 13128 KB Output is correct
5 Correct 21 ms 14220 KB Output is correct
6 Correct 471 ms 53072 KB Output is correct
7 Correct 407 ms 53212 KB Output is correct
8 Correct 170 ms 21104 KB Output is correct
9 Correct 1317 ms 33728 KB Output is correct
10 Correct 506 ms 39560 KB Output is correct
11 Correct 2706 ms 49880 KB Output is correct
12 Correct 616 ms 43708 KB Output is correct
13 Correct 404 ms 53000 KB Output is correct
14 Correct 1176 ms 37216 KB Output is correct
15 Correct 968 ms 46348 KB Output is correct
16 Correct 1492 ms 49564 KB Output is correct
17 Correct 514 ms 53336 KB Output is correct
18 Correct 1619 ms 49640 KB Output is correct
19 Correct 49 ms 15644 KB Output is correct
20 Correct 92 ms 13472 KB Output is correct
21 Correct 133 ms 13344 KB Output is correct
22 Correct 726 ms 15148 KB Output is correct
23 Correct 744 ms 15524 KB Output is correct
24 Correct 105 ms 14108 KB Output is correct
25 Correct 600 ms 13696 KB Output is correct
26 Correct 727 ms 33112 KB Output is correct
27 Correct 1395 ms 46260 KB Output is correct
28 Correct 1537 ms 52348 KB Output is correct
29 Correct 1201 ms 33756 KB Output is correct
30 Correct 2611 ms 49732 KB Output is correct
31 Correct 2091 ms 37440 KB Output is correct
32 Correct 2395 ms 49736 KB Output is correct