oj.uz

Submission #860015

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

using namespace std;

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

int n;
int h[nmax + 5];

set<pair<int,int>> s;

vector<int> l;

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.push_back(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)
    {
        l.clear();
        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({x,y})==s.end())
        {
            s.insert({x,y});
            t[x].update_per(y,+1,i + 1);
            t[y].update_per(x,+1,i + 1);
        }
        else
        {
            auto it = s.find({x,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(auto it : l)
    {
        vx.push_back(h[it]);
    }
    t[y].find_friends(v);
    vector<int> vy;
    for(auto it : l)
    {
        vy.push_back(h[it]);
    }
    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:125: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]
  125 |             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:211:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |     for(int i=0; i<vx.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:213:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         while(poz < vy.size() && vy[poz] < vx[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:217:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         if(poz >= vy.size())
      |            ~~~~^~~~~~~~~~~~
potion.cpp:224:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int i=0; i<vy.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:226:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         while(poz < vx.size() && vx[poz] < vy[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:230:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |         if(poz >= vx.size())
      |            ~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 2828 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 10 ms 3932 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 59492 KB Output is correct
2 Correct 376 ms 59264 KB Output is correct
3 Correct 244 ms 101520 KB Output is correct
4 Correct 1953 ms 242492 KB Output is correct
5 Correct 800 ms 140992 KB Output is correct
6 Correct 2603 ms 165200 KB Output is correct
7 Correct 605 ms 100116 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 59336 KB Output is correct
2 Correct 1695 ms 163928 KB Output is correct
3 Correct 1223 ms 145644 KB Output is correct
4 Correct 1965 ms 164712 KB Output is correct
5 Correct 454 ms 69804 KB Output is correct
6 Correct 2137 ms 165784 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4956 KB Output is correct
2 Correct 67 ms 7512 KB Output is correct
3 Correct 104 ms 7000 KB Output is correct
4 Correct 643 ms 9308 KB Output is correct
5 Correct 624 ms 7768 KB Output is correct
6 Correct 93 ms 8024 KB Output is correct
7 Correct 513 ms 9616 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 2828 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 10 ms 3932 KB Output is correct
6 Correct 372 ms 59492 KB Output is correct
7 Correct 376 ms 59264 KB Output is correct
8 Correct 244 ms 101520 KB Output is correct
9 Correct 1953 ms 242492 KB Output is correct
10 Correct 800 ms 140992 KB Output is correct
11 Correct 2603 ms 165200 KB Output is correct
12 Correct 605 ms 100116 KB Output is correct
13 Correct 344 ms 59336 KB Output is correct
14 Correct 1695 ms 163928 KB Output is correct
15 Correct 1223 ms 145644 KB Output is correct
16 Correct 1965 ms 164712 KB Output is correct
17 Correct 454 ms 69804 KB Output is correct
18 Correct 2137 ms 165784 KB Output is correct
19 Correct 34 ms 4956 KB Output is correct
20 Correct 67 ms 7512 KB Output is correct
21 Correct 104 ms 7000 KB Output is correct
22 Correct 643 ms 9308 KB Output is correct
23 Correct 624 ms 7768 KB Output is correct
24 Correct 93 ms 8024 KB Output is correct
25 Correct 513 ms 9616 KB Output is correct
26 Correct 864 ms 127844 KB Output is correct
27 Correct 1625 ms 145892 KB Output is correct
28 Correct 1677 ms 111472 KB Output is correct
29 Correct 1859 ms 242636 KB Output is correct
30 Execution timed out 3091 ms 165240 KB Time limit exceeded
31 Halted 0 ms 0 KB -