oj.uz

답안 #860016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860016 2023-10-11T11:24:48 Z Tenis0206 The Potion of Great Power (CEOI20_potion) C++11
70 / 100
 3000 ms 242264 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#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;

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:4: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    4 | #pragma gcc optimize("Ofast")
      | 
potion.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("Ofast")
      | 
potion.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize(Ofast)
      | 
potion.cpp: In member function 'void tr::update_per(int, int, int)':
potion.cpp:134: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]
  134 |             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:220:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |     for(int i=0; i<vx.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:222:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         while(poz < vy.size() && vy[poz] < vx[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:226:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         if(poz >= vy.size())
      |            ~~~~^~~~~~~~~~~~
potion.cpp:233:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |     for(int i=0; i<vy.size(); i++)
      |                  ~^~~~~~~~~~
potion.cpp:235:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |         while(poz < vx.size() && vx[poz] < vy[i])
      |               ~~~~^~~~~~~~~~~
potion.cpp:239:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         if(poz >= vx.size())
      |            ~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 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 4232 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 398 ms 59424 KB Output is correct
2 Correct 352 ms 59348 KB Output is correct
3 Correct 246 ms 101700 KB Output is correct
4 Correct 2005 ms 241720 KB Output is correct
5 Correct 809 ms 141148 KB Output is correct
6 Correct 2698 ms 165816 KB Output is correct
7 Correct 609 ms 100796 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 59668 KB Output is correct
2 Correct 1679 ms 162464 KB Output is correct
3 Correct 1224 ms 145868 KB Output is correct
4 Correct 2000 ms 164964 KB Output is correct
5 Correct 456 ms 69644 KB Output is correct
6 Correct 2184 ms 166060 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 4952 KB Output is correct
2 Correct 72 ms 7512 KB Output is correct
3 Correct 108 ms 6940 KB Output is correct
4 Correct 683 ms 9556 KB Output is correct
5 Correct 636 ms 7768 KB Output is correct
6 Correct 94 ms 8024 KB Output is correct
7 Correct 534 ms 9356 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 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 4232 KB Output is correct
6 Correct 398 ms 59424 KB Output is correct
7 Correct 352 ms 59348 KB Output is correct
8 Correct 246 ms 101700 KB Output is correct
9 Correct 2005 ms 241720 KB Output is correct
10 Correct 809 ms 141148 KB Output is correct
11 Correct 2698 ms 165816 KB Output is correct
12 Correct 609 ms 100796 KB Output is correct
13 Correct 364 ms 59668 KB Output is correct
14 Correct 1679 ms 162464 KB Output is correct
15 Correct 1224 ms 145868 KB Output is correct
16 Correct 2000 ms 164964 KB Output is correct
17 Correct 456 ms 69644 KB Output is correct
18 Correct 2184 ms 166060 KB Output is correct
19 Correct 32 ms 4952 KB Output is correct
20 Correct 72 ms 7512 KB Output is correct
21 Correct 108 ms 6940 KB Output is correct
22 Correct 683 ms 9556 KB Output is correct
23 Correct 636 ms 7768 KB Output is correct
24 Correct 94 ms 8024 KB Output is correct
25 Correct 534 ms 9356 KB Output is correct
26 Correct 892 ms 127720 KB Output is correct
27 Correct 1641 ms 144964 KB Output is correct
28 Correct 1679 ms 111124 KB Output is correct
29 Correct 1886 ms 242264 KB Output is correct
30 Execution timed out 3078 ms 166416 KB Time limit exceeded
31 Halted 0 ms 0 KB -