oj.uz

Submission #860019

# Submission time Handle Problem Language Result Execution time Memory
860019 2023-10-11T11:28:25 Z Tenis0206 The Potion of Great Power (CEOI20_potion) C++11
70 / 100
 3000 ms 242052 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<pair<int,int>> 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({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(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 10 ms 3672 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 59740 KB Output is correct
2 Correct 369 ms 59412 KB Output is correct
3 Correct 247 ms 101668 KB Output is correct
4 Correct 1921 ms 242052 KB Output is correct
5 Correct 767 ms 141160 KB Output is correct
6 Correct 2662 ms 166152 KB Output is correct
7 Correct 610 ms 100756 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 59700 KB Output is correct
2 Correct 1646 ms 163144 KB Output is correct
3 Correct 1202 ms 145468 KB Output is correct
4 Correct 1929 ms 164832 KB Output is correct
5 Correct 463 ms 69428 KB Output is correct
6 Correct 2102 ms 164928 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5208 KB Output is correct
2 Correct 65 ms 7768 KB Output is correct
3 Correct 106 ms 7256 KB Output is correct
4 Correct 668 ms 9372 KB Output is correct
5 Correct 644 ms 7768 KB Output is correct
6 Correct 92 ms 8024 KB Output is correct
7 Correct 523 ms 9304 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 10 ms 3672 KB Output is correct
6 Correct 369 ms 59740 KB Output is correct
7 Correct 369 ms 59412 KB Output is correct
8 Correct 247 ms 101668 KB Output is correct
9 Correct 1921 ms 242052 KB Output is correct
10 Correct 767 ms 141160 KB Output is correct
11 Correct 2662 ms 166152 KB Output is correct
12 Correct 610 ms 100756 KB Output is correct
13 Correct 358 ms 59700 KB Output is correct
14 Correct 1646 ms 163144 KB Output is correct
15 Correct 1202 ms 145468 KB Output is correct
16 Correct 1929 ms 164832 KB Output is correct
17 Correct 463 ms 69428 KB Output is correct
18 Correct 2102 ms 164928 KB Output is correct
19 Correct 32 ms 5208 KB Output is correct
20 Correct 65 ms 7768 KB Output is correct
21 Correct 106 ms 7256 KB Output is correct
22 Correct 668 ms 9372 KB Output is correct
23 Correct 644 ms 7768 KB Output is correct
24 Correct 92 ms 8024 KB Output is correct
25 Correct 523 ms 9304 KB Output is correct
26 Correct 865 ms 127972 KB Output is correct
27 Correct 1602 ms 145636 KB Output is correct
28 Correct 1663 ms 111612 KB Output is correct
29 Correct 1840 ms 241808 KB Output is correct
30 Execution timed out 3029 ms 165184 KB Time limit exceeded
31 Halted 0 ms 0 KB -