oj.uz

Submission #946288

# Submission time Handle Problem Language Result Execution time Memory
946288 2024-03-14T13:22:53 Z JooDdae The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 99120 KB 
#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;
}

Compilation message

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 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 22 ms 10236 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 98432 KB Output is correct
2 Correct 400 ms 99120 KB Output is correct
3 Correct 264 ms 97988 KB Output is correct
4 Correct 2575 ms 62208 KB Output is correct
5 Correct 995 ms 79712 KB Output is correct
6 Execution timed out 3040 ms 97720 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 98996 KB Output is correct
2 Execution timed out 3039 ms 98620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9308 KB Output is correct
2 Correct 137 ms 9752 KB Output is correct
3 Correct 230 ms 9500 KB Output is correct
4 Correct 1114 ms 9480 KB Output is correct
5 Correct 1002 ms 9560 KB Output is correct
6 Correct 157 ms 9048 KB Output is correct
7 Correct 911 ms 9820 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 22 ms 10236 KB Output is correct
6 Correct 398 ms 98432 KB Output is correct
7 Correct 400 ms 99120 KB Output is correct
8 Correct 264 ms 97988 KB Output is correct
9 Correct 2575 ms 62208 KB Output is correct
10 Correct 995 ms 79712 KB Output is correct
11 Execution timed out 3040 ms 97720 KB Time limit exceeded
12 Halted 0 ms 0 KB -