oj.uz

Submission #860020

# Submission time Handle Problem Language Result Execution time Memory
860020 2023-10-11T11:30:19 Z Tenis0206 The Potion of Great Power (CEOI20_potion) C++11
70 / 100
 3000 ms 245920 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];

map <pair<int,int>, bool> mp;

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(!mp[{x,y}])
        {
            mp[{x,y}] = true;
            t[x].update_per(y,+1,i + 1);
            t[y].update_per(x,+1,i + 1);
        }
        else
        {
            mp[{x,y}] = false;
            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:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for(int i=0; i<vx.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |         while(poz < vy.size() && vy[poz] < vx[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:222:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         if(poz >= vy.size())
      |            ~~~~^~~~~~~~~~~~
potion.cpp:229:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(int i=0; i<vy.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:231:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |         while(poz < vx.size() && vx[poz] < vy[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:235:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |         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 4016 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 62940 KB Output is correct
2 Correct 424 ms 62968 KB Output is correct
3 Correct 237 ms 102000 KB Output is correct
4 Correct 2138 ms 245920 KB Output is correct
5 Correct 862 ms 144652 KB Output is correct
6 Correct 2899 ms 169464 KB Output is correct
7 Correct 657 ms 103544 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 62756 KB Output is correct
2 Correct 1726 ms 165940 KB Output is correct
3 Correct 1251 ms 148496 KB Output is correct
4 Correct 2025 ms 167764 KB Output is correct
5 Correct 463 ms 72608 KB Output is correct
6 Correct 2267 ms 168672 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5208 KB Output is correct
2 Correct 66 ms 7768 KB Output is correct
3 Correct 106 ms 6816 KB Output is correct
4 Correct 683 ms 9932 KB Output is correct
5 Correct 677 ms 7940 KB Output is correct
6 Correct 95 ms 8024 KB Output is correct
7 Correct 526 ms 9372 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 4016 KB Output is correct
6 Correct 454 ms 62940 KB Output is correct
7 Correct 424 ms 62968 KB Output is correct
8 Correct 237 ms 102000 KB Output is correct
9 Correct 2138 ms 245920 KB Output is correct
10 Correct 862 ms 144652 KB Output is correct
11 Correct 2899 ms 169464 KB Output is correct
12 Correct 657 ms 103544 KB Output is correct
13 Correct 439 ms 62756 KB Output is correct
14 Correct 1726 ms 165940 KB Output is correct
15 Correct 1251 ms 148496 KB Output is correct
16 Correct 2025 ms 167764 KB Output is correct
17 Correct 463 ms 72608 KB Output is correct
18 Correct 2267 ms 168672 KB Output is correct
19 Correct 34 ms 5208 KB Output is correct
20 Correct 66 ms 7768 KB Output is correct
21 Correct 106 ms 6816 KB Output is correct
22 Correct 683 ms 9932 KB Output is correct
23 Correct 677 ms 7940 KB Output is correct
24 Correct 95 ms 8024 KB Output is correct
25 Correct 526 ms 9372 KB Output is correct
26 Correct 946 ms 130844 KB Output is correct
27 Correct 1825 ms 148344 KB Output is correct
28 Correct 1890 ms 115272 KB Output is correct
29 Correct 2095 ms 245832 KB Output is correct
30 Execution timed out 3051 ms 168892 KB Time limit exceeded
31 Halted 0 ms 0 KB -