제출 #946288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946288		JooDdae	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3040 ms	99120 KiB

potion

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

struct Node {
    int l, r, s;
} pt[20010010];
int pc;

int n, D, h[100100], r[100100];
array<int, 2> p[100100];
vector<pair<int, int>> d[100100];

int update(int u, int id, int val, int l = 0, int r = n-1) {
    if(id < l || r < id) return u;

    int x = ++pc;
    pt[x] = pt[u], pt[x].s += val;
    if(l == r) return x;

    pt[x].l = update(pt[x].l, id, val, l, mid);
    pt[x].r = update(pt[x].r, id, val, mid+1, r);
    return x;
}

int find(int u, int id, int l = 0, int r = n-1) {
    if(id < l || r < id) return 0;
    if(l == r) return pt[u].s;
    return find(pt[u].l, id, l, mid) + find(pt[u].r, id, mid+1, r);
}

void find_all(int u, vector<int> &v, int l = 0, int r = n-1) {
    if(l == r) {
        v.push_back(l);
        return;
    }

    if(pt[pt[u].l].s) find_all(pt[u].l, v, l, mid);
    if(pt[pt[u].r].s) find_all(pt[u].r, v, mid+1, r);
}

void init(int N, int D, int H[]) {
    n = N, ::D = D;

    for(int i=0;i<N;i++) p[i] = {H[i], i};
    sort(p, p+N);

    for(int i=0;i<N;i++) h[i] = p[i][0], r[p[i][1]] = i, d[i].push_back({0, 0});
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=1;i<=U;i++) {
        int x = r[A[i-1]], y = r[B[i-1]];

        int rx = d[x].back().second, ry = d[y].back().second;

        int c = find(rx, y) ? -1 : 1;
        d[x].push_back({i, update(rx, y, c)});
        d[y].push_back({i, update(ry, x, c)});
    }
}

int question(int x, int y, int v) {
    x = r[x], y = r[y];
    int ans = 1e9;

    auto rx = prev(upper_bound(d[x].begin(), d[x].end(), make_pair(v+1, 0)))->second;
    auto ry = prev(upper_bound(d[y].begin(), d[y].end(), make_pair(v+1, 0)))->second;

    int cx = pt[rx].s, cy = pt[ry].s;
    vector<int> X, Y;
    find_all(rx, X), find_all(ry, Y);

    x = 0, y = 0;
    while(x < X.size() && y < Y.size()) {
        ans = min(ans, abs(h[X[x]] - h[Y[y]]));

        if(h[X[x]] < h[Y[y]]) x++;
        else y++;
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:77:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(x < X.size() && y < Y.size()) {
      |           ~~^~~~~~~~~~
potion.cpp:77:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(x < X.size() && y < Y.size()) {
      |                           ~~^~~~~~~~~~
potion.cpp:72:9: warning: unused variable 'cx' [-Wunused-variable]
   72 |     int cx = pt[rx].s, cy = pt[ry].s;
      |         ^~
potion.cpp:72:24: warning: unused variable 'cy' [-Wunused-variable]
   72 |     int cx = pt[rx].s, cy = pt[ry].s;
      |                        ^~

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30