oj.uz

답안 #660977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660977 2022-11-23T18:57:22 Z Lobo The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 890 ms 58372 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 = 15;

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

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9936 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 9 ms 9892 KB Output is correct
4 Correct 43 ms 22832 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 37860 KB Output is correct
2 Correct 267 ms 37636 KB Output is correct
3 Correct 201 ms 30680 KB Output is correct
4 Correct 437 ms 36760 KB Output is correct
5 Correct 263 ms 24212 KB Output is correct
6 Correct 763 ms 58248 KB Output is correct
7 Correct 341 ms 38472 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 37744 KB Output is correct
2 Correct 626 ms 54384 KB Output is correct
3 Correct 506 ms 47400 KB Output is correct
4 Correct 592 ms 58360 KB Output is correct
5 Correct 279 ms 39424 KB Output is correct
6 Correct 626 ms 58304 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 11984 KB Output is correct
2 Correct 126 ms 11420 KB Output is correct
3 Correct 160 ms 11476 KB Output is correct
4 Correct 280 ms 12404 KB Output is correct
5 Correct 251 ms 12372 KB Output is correct
6 Correct 148 ms 10344 KB Output is correct
7 Correct 289 ms 11864 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 10 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 43 ms 22832 KB Output is correct
6 Correct 293 ms 37860 KB Output is correct
7 Correct 267 ms 37636 KB Output is correct
8 Correct 201 ms 30680 KB Output is correct
9 Correct 437 ms 36760 KB Output is correct
10 Correct 263 ms 24212 KB Output is correct
11 Correct 763 ms 58248 KB Output is correct
12 Correct 341 ms 38472 KB Output is correct
13 Correct 253 ms 37744 KB Output is correct
14 Correct 626 ms 54384 KB Output is correct
15 Correct 506 ms 47400 KB Output is correct
16 Correct 592 ms 58360 KB Output is correct
17 Correct 279 ms 39424 KB Output is correct
18 Correct 626 ms 58304 KB Output is correct
19 Correct 51 ms 11984 KB Output is correct
20 Correct 126 ms 11420 KB Output is correct
21 Correct 160 ms 11476 KB Output is correct
22 Correct 280 ms 12404 KB Output is correct
23 Correct 251 ms 12372 KB Output is correct
24 Correct 148 ms 10344 KB Output is correct
25 Correct 289 ms 11864 KB Output is correct
26 Correct 471 ms 40652 KB Output is correct
27 Correct 606 ms 47332 KB Output is correct
28 Correct 588 ms 48108 KB Output is correct
29 Correct 538 ms 36840 KB Output is correct
30 Correct 861 ms 58332 KB Output is correct
31 Correct 741 ms 54656 KB Output is correct
32 Correct 890 ms 58372 KB Output is correct