oj.uz

Submission #660978

# Submission time Handle Problem Language Result Execution time Memory
660978 2022-11-23T18:57:33 Z Lobo The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 906 ms 64196 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define ll long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, a[maxn], idord[maxn];
vector<pair<int,int>> ord;

vector<pair<int,int>> g[maxn];
vector<pair<int,vector<int>>> frds[maxn];
const int BC = 12;

void init(int N, int D, int H[]) {
    n = N;
    for(int i = 0; i < n; i++) {
        ord.pb(mp(H[i],i));
    }
    sort(all(ord));
    for(int i = 0; i < n; i++) {
        idord[ord[i].sc] = i;
        a[i] = ord[i].fr;
    }
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; i++) {
        int u = idord[A[i]];
        int v = idord[B[i]];

        g[u].pb(mp(i+1,v));
        g[v].pb(mp(i+1,u));
    }

    for(int i = 0; i < n; i++) {
        set<int> st;
        int cnt = 0;
        frds[i].pb(mp(0,vector<int>{}));
        for(auto X : g[i]) {
            int j = X.sc;
            int id = X.fr;
            if(st.count(j)) st.erase(j);
            else st.insert(j);

            if(++cnt == BC || g[i].back().fr == id) {
                frds[i].pb(mp(id,vector<int>{}));
                for(auto x : st) {
                    frds[i].back().sc.pb(x);
                }
                cnt = 0;
            }
        }
        frds[i].pb(mp(U+1,vector<int>{}));
        g[i].pb(mp(U+1,-1));

        // cout << i << "  " << a[i] << endl;
        // for(auto x : frds[i]) {
        //     cout << " " << x.fr << endl;
        // }
    }
}

int question(int x, int y, int v) {
    x = idord[x];
    y = idord[y];

    vector<int> vcx, vcx0, vcx1;
    auto itfrx = prev(lower_bound(all(frds[x]),mp(v+1,vector<int>{})));
    vcx0 = itfrx->sc;
    // vcx = vcx0;
    set<int> stx;
    for(auto it = lower_bound(all(g[x]),mp(itfrx->fr+1,-1)); it->fr <= v; it++) {
        int i = it->sc;
        if(stx.count(i)) stx.erase(i);
        else stx.insert(i);
    }
    // assert(stx.size() == 0);
    for(auto i : stx) vcx1.pb(i); 
    int i0 = 0;
    int i1 = 0;
    while(i0 != vcx0.size() && i1 != vcx1.size()) {
        if(vcx0[i0] < vcx1[i1]) {
            vcx.pb(vcx0[i0]);
            i0++;
        }
        else if(vcx0[i0] > vcx1[i1]) {
            vcx.pb(vcx1[i1]);
            i1++;
        }
        else {
            i0++;
            i1++;
        }
    }
    while(i0 != vcx0.size()) {
        vcx.pb(vcx0[i0]);
        i0++;
    }
    while(i1 != vcx1.size()) {
        vcx.pb(vcx1[i1]);
        i1++;
    }

    // cout << x << " " << " x " << prev(lower_bound(all(frds[x]),mp(v+1,vector<int>{})))->fr << endl;
    vector<int> vcy, vcy0, vcy1;
    auto itfry = prev(lower_bound(all(frds[y]),mp(v+1,vector<int>{})));
    vcy0 = itfry->sc;
    // vcy = vcy0;
    set<int> sty;    
    for(auto it = lower_bound(all(g[y]),mp(itfry->fr+1,-1)); it->fr <= v; it++) {
        int i = it->sc;
        if(sty.count(i)) sty.erase(i);
        else sty.insert(i);
    }
    for(auto i : sty) vcy1.pb(i); 
    int j0 = 0;
    int j1 = 0;
    while(j0 != vcy0.size() && j1 != vcy1.size()) {
        if(vcy0[j0] < vcy1[j1]) {
            vcy.pb(vcy0[j0]);
            j0++;
        }
        else if(vcy0[j0] > vcy1[j1]) {
            vcy.pb(vcy1[j1]);
            j1++;
        }
        else {
            j0++;
            j1++;
        }
    }
    while(j0 != vcy0.size()) {
        vcy.pb(vcy0[j0]);
        j0++;
    }
    while(j1 != vcy1.size()) {
        vcy.pb(vcy1[j1]);
        j1++;
    }
    // cout << " y " << prev(lower_bound(all(frds[y]),mp(v+1,vector<int>{})))->fr << endl;

    if(vcx.size() == 0) return 1000000000;
    if(vcy.size() == 0) return 1000000000;

    int i = 0;
    int j = 0;
    int ans = inf1;
    while(i != vcx.size() && j != vcy.size()) {
        ans = min(ans, abs(a[vcx[i]]-a[vcy[j]]));
        if(a[vcx[i]] < a[vcy[j]]) {
            //increase i
            i++;
        }
        else {
            j++;
        }
    }

    return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while(i0 != vcx0.size() && i1 != vcx1.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:91:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while(i0 != vcx0.size() && i1 != vcx1.size()) {
      |                                ~~~^~~~~~~~~~~~~~
potion.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     while(i0 != vcx0.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:109:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     while(i1 != vcx1.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:128:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while(j0 != vcy0.size() && j1 != vcy1.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:128:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while(j0 != vcy0.size() && j1 != vcy1.size()) {
      |                                ~~~^~~~~~~~~~~~~~
potion.cpp:142:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     while(j0 != vcy0.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     while(j1 != vcy1.size()) {
      |           ~~~^~~~~~~~~~~~~~
potion.cpp:158:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     while(i != vcx.size() && j != vcy.size()) {
      |           ~~^~~~~~~~~~~~~
potion.cpp:158:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     while(i != vcx.size() && j != vcy.size()) {
      |                              ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9936 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 8 ms 9936 KB Output is correct
4 Correct 62 ms 22824 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 37744 KB Output is correct
2 Correct 315 ms 37744 KB Output is correct
3 Correct 197 ms 31124 KB Output is correct
4 Correct 474 ms 42552 KB Output is correct
5 Correct 265 ms 25988 KB Output is correct
6 Correct 819 ms 64072 KB Output is correct
7 Correct 317 ms 39612 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 37744 KB Output is correct
2 Correct 559 ms 60044 KB Output is correct
3 Correct 510 ms 50268 KB Output is correct
4 Correct 625 ms 64196 KB Output is correct
5 Correct 324 ms 39892 KB Output is correct
6 Correct 692 ms 64112 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11988 KB Output is correct
2 Correct 122 ms 11472 KB Output is correct
3 Correct 138 ms 11400 KB Output is correct
4 Correct 261 ms 12488 KB Output is correct
5 Correct 237 ms 12548 KB Output is correct
6 Correct 170 ms 10448 KB Output is correct
7 Correct 235 ms 11912 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 8 ms 9936 KB Output is correct
5 Correct 62 ms 22824 KB Output is correct
6 Correct 272 ms 37744 KB Output is correct
7 Correct 315 ms 37744 KB Output is correct
8 Correct 197 ms 31124 KB Output is correct
9 Correct 474 ms 42552 KB Output is correct
10 Correct 265 ms 25988 KB Output is correct
11 Correct 819 ms 64072 KB Output is correct
12 Correct 317 ms 39612 KB Output is correct
13 Correct 261 ms 37744 KB Output is correct
14 Correct 559 ms 60044 KB Output is correct
15 Correct 510 ms 50268 KB Output is correct
16 Correct 625 ms 64196 KB Output is correct
17 Correct 324 ms 39892 KB Output is correct
18 Correct 692 ms 64112 KB Output is correct
19 Correct 56 ms 11988 KB Output is correct
20 Correct 122 ms 11472 KB Output is correct
21 Correct 138 ms 11400 KB Output is correct
22 Correct 261 ms 12488 KB Output is correct
23 Correct 237 ms 12548 KB Output is correct
24 Correct 170 ms 10448 KB Output is correct
25 Correct 235 ms 11912 KB Output is correct
26 Correct 446 ms 43104 KB Output is correct
27 Correct 572 ms 50304 KB Output is correct
28 Correct 564 ms 50792 KB Output is correct
29 Correct 554 ms 42548 KB Output is correct
30 Correct 906 ms 64100 KB Output is correct
31 Correct 824 ms 60552 KB Output is correct
32 Correct 787 ms 64140 KB Output is correct