oj.uz

Submission #860023

# Submission time Handle Problem Language Result Execution time Memory
860023 2023-10-11T11:32:55 Z Tenis0206 The Potion of Great Power (CEOI20_potion) C++11
70 / 100
 3000 ms 242532 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC push_options
#pragma GCC pop_options

using namespace std;

const int nmax = 1e5;
const int oo = 1e9;

int n;
int h[nmax + 5];

set<long long> s;

int l[nmax + 5];
int nrl = 0;

mt19937 my_rand(time(NULL));

struct Node
{
    Node *st, *dr;
    int val;
    int prior;
};

struct tr
{
    vector<pair<int,Node*>> r;
    Node *mod_fiu(Node *nod, int care, Node *f)
    {
        if(care==0)
        {
            nod -> st = f;
        }
        else
        {
            nod -> dr = f;
        }
        return nod;
    }
    pair<Node*,Node*> split(Node *nod, int val)
    {
        if(!nod)
        {
            return {nullptr, nullptr};
        }
        if(val < nod->val)
        {
            if(nod->st)
            {
                nod->st = new Node{nod->st->st, nod->st->dr, nod->st->val, nod->st->prior};
                auto t = split(nod -> st, val);
                return {t.first,mod_fiu(nod,0,t.second)};
            }
            return {nullptr, mod_fiu(nod,0,nullptr)};
        }
        else
        {
            if(nod->dr)
            {
                nod->dr = new Node{nod->dr->st, nod->dr->dr, nod->dr->val, nod->dr->prior};
                auto t = split(nod -> dr, val);
                return {mod_fiu(nod,1,t.first),t.second};
            }
            return {mod_fiu(nod,1,nullptr), nullptr};
        }
    }
    Node *join(Node *st, Node *dr)
    {
        if(!st)
        {
            return dr;
        }
        if(!dr)
        {
            return st;
        }
        if(st->prior>=dr->prior)
        {
            if(st->dr)
            {
                st->dr = new Node{st->dr->st, st->dr->dr, st->dr->val, st->dr->prior};
            }
            return mod_fiu(st,1,join(st->dr,dr));
        }
        else
        {
            if(dr->st)
            {
                dr->st = new Node{dr->st->st, dr->st->dr, dr->st->val, dr->st->prior};
            }
            return mod_fiu(dr,0,join(st,dr->st));
        }
    }
    void parcurg(Node *nod)
    {
        if(nod == nullptr)
        {
            return;
        }
        l[++nrl] = nod->val;
        if(nod->st)
        {
            parcurg(nod->st);
        }
        if(nod->dr)
        {
            parcurg(nod->dr);
        }
    }
    void update_per(int poz, int val, int nr)
    {
        pair<int, Node*> cur = {nr, nullptr};
        if(r.size() && r.back().second)
        {
            cur = {nr,new Node{r.back().second->st,r.back().second->dr,r.back().second->val,r.back().second->prior}};
        }
        if(val==0)
        {
            auto t = split(cur.second, poz - 1);
            auto t2 = split(t.second, poz);
            cur.second = join(t.first,t2.second);
        }
        else
        {
            auto t = split(cur.second, poz);
            cur.second = join(join(t.first, new Node{nullptr,nullptr,poz,my_rand()}), t.second);
        }
        r.push_back(cur);
    }
    void find_friends(int v)
    {
        nrl = 0;
        int st = 0;
        int dr = r.size() - 1;
        int poz = -1;
        while(st<=dr)
        {
            int mij = (st + dr) >> 1;
            if(r[mij].first <= v)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        if(poz==-1)
        {
            return;
        }
        parcurg(r[poz].second);
    }
};

tr t[nmax + 5];

void init(int N, int D, int H[])
{
    n = N;
    for(int i=0; i<n; i++)
    {
        h[i] = H[i];
    }
}

void curseChanges(int U, int A[], int B[])
{
    for(int i=0; i<U; i++)
    {
        int x = A[i];
        int y = B[i];
        if(x > y)
        {
            swap(x,y);
        }
        if(s.find(1LL * x * nmax + y)==s.end())
        {
            s.insert(1LL * x * nmax + y);
            t[x].update_per(y,+1,i + 1);
            t[y].update_per(x,+1,i + 1);
        }
        else
        {
            auto it = s.find(1LL * x * nmax + y);
            s.erase(it);
            t[x].update_per(y,0,i + 1);
            t[y].update_per(x,0,i + 1);
        }
    }
}

int question(int x, int y, int v)
{
    t[x].find_friends(v);
    vector<int> vx;
    for(int i=1;i<=nrl;i++)
    {
        vx.push_back(h[l[i]]);
    }
    t[y].find_friends(v);
    vector<int> vy;
    for(int i=1;i<=nrl;i++)
    {
        vy.push_back(h[l[i]]);
    }
    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());
    int rez = oo;
    int poz = 0;
    for(int i=0; i<vx.size(); i++)
    {
        while(poz < vy.size() && vy[poz] < vx[i])
        {
            ++poz;
        }
        if(poz >= vy.size())
        {
            break;
        }
        rez = min(rez, vy[poz] - vx[i]);
    }
    poz = 0;
    for(int i=0; i<vy.size(); i++)
    {
        while(poz < vx.size() && vx[poz] < vy[i])
        {
            ++poz;
        }
        if(poz >= vx.size())
        {
            break;
        }
        rez = min(rez, vx[poz] - vy[i]);
    }
    return rez;
}

Compilation message

potion.cpp: In member function 'void tr::update_per(int, int, int)':
potion.cpp:131:81: warning: narrowing conversion of 'my_rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  131 |             cur.second = join(join(t.first, new Node{nullptr,nullptr,poz,my_rand()}), t.second);
      |                                                                          ~~~~~~~^~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:217:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |     for(int i=0; i<vx.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:219:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |         while(poz < vy.size() && vy[poz] < vx[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:223:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         if(poz >= vy.size())
      |            ~~~~^~~~~~~~~~~~
potion.cpp:230:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |     for(int i=0; i<vy.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:232:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |         while(poz < vx.size() && vx[poz] < vy[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:236:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |         if(poz >= vx.size())
      |            ~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 11 ms 3968 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 59264 KB Output is correct
2 Correct 373 ms 59308 KB Output is correct
3 Correct 236 ms 101592 KB Output is correct
4 Correct 2052 ms 242532 KB Output is correct
5 Correct 795 ms 140976 KB Output is correct
6 Correct 2741 ms 165384 KB Output is correct
7 Correct 618 ms 100176 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 59192 KB Output is correct
2 Correct 1679 ms 162532 KB Output is correct
3 Correct 1242 ms 146068 KB Output is correct
4 Correct 2007 ms 164656 KB Output is correct
5 Correct 447 ms 69636 KB Output is correct
6 Correct 2106 ms 165128 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4952 KB Output is correct
2 Correct 64 ms 7464 KB Output is correct
3 Correct 102 ms 6744 KB Output is correct
4 Correct 672 ms 9372 KB Output is correct
5 Correct 648 ms 7768 KB Output is correct
6 Correct 94 ms 8032 KB Output is correct
7 Correct 533 ms 9768 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 11 ms 3968 KB Output is correct
6 Correct 416 ms 59264 KB Output is correct
7 Correct 373 ms 59308 KB Output is correct
8 Correct 236 ms 101592 KB Output is correct
9 Correct 2052 ms 242532 KB Output is correct
10 Correct 795 ms 140976 KB Output is correct
11 Correct 2741 ms 165384 KB Output is correct
12 Correct 618 ms 100176 KB Output is correct
13 Correct 365 ms 59192 KB Output is correct
14 Correct 1679 ms 162532 KB Output is correct
15 Correct 1242 ms 146068 KB Output is correct
16 Correct 2007 ms 164656 KB Output is correct
17 Correct 447 ms 69636 KB Output is correct
18 Correct 2106 ms 165128 KB Output is correct
19 Correct 33 ms 4952 KB Output is correct
20 Correct 64 ms 7464 KB Output is correct
21 Correct 102 ms 6744 KB Output is correct
22 Correct 672 ms 9372 KB Output is correct
23 Correct 648 ms 7768 KB Output is correct
24 Correct 94 ms 8032 KB Output is correct
25 Correct 533 ms 9768 KB Output is correct
26 Correct 846 ms 127964 KB Output is correct
27 Correct 1571 ms 145792 KB Output is correct
28 Correct 1644 ms 111216 KB Output is correct
29 Correct 1874 ms 241592 KB Output is correct
30 Execution timed out 3046 ms 165168 KB Time limit exceeded
31 Halted 0 ms 0 KB -