oj.uz

답안 #590202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590202 2022-07-05T16:20:47 Z piOOE The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1369 ms 33448 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxN = 100000, maxU = 200000, INF = 1000000000, BL = 100;

int a[maxU], b[maxU], h[maxN], n, u;

bool cmp(int i, int j) {
    return (h[i] != h[j] ? h[i] < h[j] : i < j);
}

vector<int> mrg(vector<int>& A, vector<int>& B) {
    vector<int> C(A.size() + B.size()), ans;
    merge(A.begin(), A.end(), B.begin(), B.end(), C.begin(), cmp);
    for (int i = 0; i < C.size();) {
        int j = i;
        while (j < C.size() && C[j] == C[i]) {
            j += 1;
        }
        if ((j - i) & 1) {
            ans.push_back(C[i]);
        }
        i = j;
    }
    return ans;
}

vector<vector<int>> g[maxN];

vector<int> temp[maxN];

vector<int> ti[maxN];
vector<pair<int, int>> c[maxN];

void init(int N, int D, int H[]) {
    n = N;
    memcpy(h, H, sizeof(h[0]) * n);
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    vector<int> empt;
    memcpy(a, A, sizeof(a[0]) * u), memcpy(b, B, sizeof(b[0]) * u);
    set<pair<int, int>> adj;
    for (int i = 0; i < u; ++i) {
        if (a[i] > b[i]) {
            swap(a[i], b[i]);
        }
        auto upd = [&](int x, int y) {
            temp[x].push_back(y);
            c[x].emplace_back(y, i + 1);
            if (c[x].size() % BL == 0) {
                sort(temp[x].begin(), temp[x].end(), cmp);
                g[x].push_back(mrg(g[x].empty() ? empt : g[x].back(), temp[x]));
                ti[x].push_back(i + 1);
                temp[x].clear();
            }
        };
        upd(a[i], b[i]), upd(b[i], a[i]);
        if (adj.count({a[i], b[i]})) {
            adj.erase({a[i], b[i]});
        } else {
            adj.insert({a[i], b[i]});
        }
    }
}

vector<int> get(int x, int v) {
    int it = upper_bound(ti[x].begin(), ti[x].end(), v) - ti[x].begin() - 1, t = 0;
    vector<int> ans;
    if (it > -1) {
        ans = g[x][it];
        t = ti[x][it] + 1;
    }
    it = lower_bound(c[x].begin(), c[x].end(), make_pair(-1, t), [](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    }) - c[x].begin();
    vector<int> nw;
    for (; it < int(c[x].size()) && c[x][it].second <= v; ++it) {
        auto [y, tt] = c[x][it];
        nw.push_back(y);
    }
    sort(nw.begin(), nw.end(), cmp);
    return mrg(ans, nw);
}

int question(int x, int y, int v) {
    int ans = INF;
    vector<int> f = get(x, v), s = get(y, v);
    int pnt = 0;
    for (int to: f) {
        while (pnt < s.size() && h[s[pnt]] < h[to]) {
            pnt += 1;
        }
        if (pnt < s.size()) {
            ans = min(ans, h[s[pnt]] - h[to]);
        }
        if (pnt > 0) {
            ans = min(ans, h[to] - h[s[pnt - 1]]);
        }
    }
    return ans;
}

Compilation message

potion.cpp: In function 'std::vector<int> mrg(std::vector<int>&, std::vector<int>&)':
potion.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < C.size();) {
      |                     ~~^~~~~~~~~~
potion.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while (j < C.size() && C[j] == C[i]) {
      |                ~~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (pnt < s.size() && h[s[pnt]] < h[to]) {
      |                ~~~~^~~~~~~~~~
potion.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if (pnt < s.size()) {
      |             ~~~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Correct 7 ms 9808 KB Output is correct
3 Correct 7 ms 9808 KB Output is correct
4 Correct 17 ms 10664 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 33448 KB Output is correct
2 Correct 439 ms 33352 KB Output is correct
3 Correct 446 ms 17720 KB Output is correct
4 Correct 953 ms 25292 KB Output is correct
5 Correct 490 ms 30064 KB Output is correct
6 Correct 1285 ms 27852 KB Output is correct
7 Correct 862 ms 25524 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 447 ms 33336 KB Output is correct
2 Correct 920 ms 23340 KB Output is correct
3 Correct 851 ms 26312 KB Output is correct
4 Correct 1018 ms 27868 KB Output is correct
5 Correct 541 ms 33224 KB Output is correct
6 Correct 1047 ms 27860 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 11008 KB Output is correct
2 Correct 205 ms 10284 KB Output is correct
3 Correct 378 ms 10240 KB Output is correct
4 Correct 592 ms 10792 KB Output is correct
5 Correct 466 ms 10932 KB Output is correct
6 Correct 148 ms 10704 KB Output is correct
7 Correct 558 ms 10420 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 7 ms 9808 KB Output is correct
4 Correct 7 ms 9808 KB Output is correct
5 Correct 17 ms 10664 KB Output is correct
6 Correct 452 ms 33448 KB Output is correct
7 Correct 439 ms 33352 KB Output is correct
8 Correct 446 ms 17720 KB Output is correct
9 Correct 953 ms 25292 KB Output is correct
10 Correct 490 ms 30064 KB Output is correct
11 Correct 1285 ms 27852 KB Output is correct
12 Correct 862 ms 25524 KB Output is correct
13 Correct 447 ms 33336 KB Output is correct
14 Correct 920 ms 23340 KB Output is correct
15 Correct 851 ms 26312 KB Output is correct
16 Correct 1018 ms 27868 KB Output is correct
17 Correct 541 ms 33224 KB Output is correct
18 Correct 1047 ms 27860 KB Output is correct
19 Correct 51 ms 11008 KB Output is correct
20 Correct 205 ms 10284 KB Output is correct
21 Correct 378 ms 10240 KB Output is correct
22 Correct 592 ms 10792 KB Output is correct
23 Correct 466 ms 10932 KB Output is correct
24 Correct 148 ms 10704 KB Output is correct
25 Correct 558 ms 10420 KB Output is correct
26 Correct 667 ms 21596 KB Output is correct
27 Correct 911 ms 26360 KB Output is correct
28 Correct 955 ms 31336 KB Output is correct
29 Correct 943 ms 25328 KB Output is correct
30 Correct 1369 ms 27868 KB Output is correct
31 Correct 1107 ms 23288 KB Output is correct
32 Correct 1165 ms 27868 KB Output is correct