oj.uz

Submission #1113244

# Submission time Handle Problem Language Result Execution time Memory
1113244 2024-11-16T08:06:47 Z Zero_OP The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 3000 ms 185816 KB 
#include <bits/stdc++.h>

using namespace std;

namespace persistent_segment_tree{
    struct node{
        int ln, rn, sum;
        node() : ln(0), rn(0), sum(0) {}
    };


    const int max_updates = 4e5 + 5;
    vector<node> nd;

    void init_memory(){
        nd.reserve(max_updates * 17);
    }

    int size(){
        return (int)nd.size();
    }

    void refine(int cur){
        nd[cur].sum = nd[nd[cur].ln].sum + nd[nd[cur].rn].sum;
    }

    int build(int l, int r){
        if(l == r){
            int cur = size();
            nd.emplace_back();
            return cur;
        }

        int mid = l + r >> 1;
        int ln = build(l, mid);
        int rn = build(mid + 1, r);
        int cur = size();
        nd.emplace_back();

        nd[cur].ln = ln;
        nd[cur].rn = rn;
        return cur;
    }

    int update(int old, int l, int r, int pos, int val){
        if(l == r){
            int cur = size();
            nd.emplace_back();
            nd[cur].sum = nd[old].sum + val;
            return cur;
        }

        int mid = l + r >> 1;
        int ln = (pos <= mid ? update(nd[old].ln, l, mid, pos, val) : nd[old].ln);
        int rn = (mid < pos ? update(nd[old].rn, mid + 1, r, pos, val) : nd[old].rn);
        int cur = size();
        nd.emplace_back();

        nd[cur].ln = ln;
        nd[cur].rn = rn;
        refine(cur);
        return cur;
    }

    void get_active(int cur, int l, int r, vector<int>& res){
        if(l == r){
            if(nd[cur].sum) res.push_back(l);
        } else{
            int mid = l + r >> 1;
            if(nd[nd[cur].ln].sum) get_active(nd[cur].ln, l, mid, res);
            if(nd[nd[cur].rn].sum) get_active(nd[cur].rn, mid + 1, r, res);
        }
    }
}

using namespace persistent_segment_tree;

const int MAXN = 1e5 + 5;
const int MAXQ = 2e5 + 5;

int N, D, H[MAXN], pos[MAXN];
vector<int> modified_time[MAXN];
vector<int> root[MAXN];

void init(int _N, int _D, int _H[]){
    N = _N;
    D = _D;
    copy(_H, _H + N, H);

    vector<pair<int, int>> v;
    for(int i = 0; i < N; ++i){
        v.emplace_back(H[i], i);
    }

    sort(v.begin(), v.end());
    sort(H, H + N);
    for(int i = 0; i < N; ++i){
        pos[v[i].second] = i;
    }

    init_memory();
}

void curseChanges(int U, int A[], int B[]){
    int zero_ver = build(0, N - 1);
    for(int i = 0; i < N; ++i){
        modified_time[i].emplace_back(0);
        root[i].emplace_back(i);
    }

    set<pair<int, int>> pairs;

    for(int i = 0; i < U; ++i){
        int u = A[i], v = B[i];
        u = pos[u]; v = pos[v];
        modified_time[u].emplace_back(i + 1);
        modified_time[v].emplace_back(i + 1);
        if(u > v) swap(u, v);
        if(pairs.count({u, v})){
            root[u].emplace_back(update(root[u].back(), 0, N - 1, v, -1));
            root[v].emplace_back(update(root[v].back(), 0, N - 1, u, -1));
            pairs.erase({u, v});
        } else{
            root[u].emplace_back(update(root[u].back(), 0, N - 1, v, 1));
            root[v].emplace_back(update(root[v].back(), 0, N - 1, u, 1));
            pairs.insert({u, v});
        }
    }
}

vector<int> A, B;

int question(int x, int y, int v){
    x = pos[x]; y = pos[y];
    int p = upper_bound(modified_time[x].begin(), modified_time[x].end(), v) - modified_time[x].begin() - 1;
    int q = upper_bound(modified_time[y].begin(), modified_time[y].end(), v) - modified_time[y].begin() - 1;
    assert(p >= 0 && q >= 0);
    vector<int>().swap(A);
    vector<int>().swap(B);

    get_active(root[x][p], 0, N - 1, A);
    get_active(root[y][q], 0, N - 1, B);
    if(A.empty() && B.empty()) return (int)1e9;

    int ans = (int)1e9;
    int ptr = 0;
    for(int i = 0; i < (int)A.size(); ++i){
        while(ptr < (int)B.size() && B[ptr] < A[i]) ++ptr;
        if(ptr < (int)B.size()) ans = min(ans, abs(H[A[i]] - H[B[ptr]]));
        if(ptr - 1 >= 0) ans = min(ans, abs(H[A[i]] - H[B[ptr - 1]]));
    }

    return ans;
}

Compilation message

potion.cpp: In function 'int persistent_segment_tree::build(int, int)':
potion.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid = l + r >> 1;
      |                   ~~^~~
potion.cpp: In function 'int persistent_segment_tree::update(int, int, int, int, int)':
potion.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = l + r >> 1;
      |                   ~~^~~
potion.cpp: In function 'void persistent_segment_tree::get_active(int, int, int, std::vector<int>&)':
potion.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |             int mid = l + r >> 1;
      |                       ~~^~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:105:9: warning: unused variable 'zero_ver' [-Wunused-variable]
  105 |     int zero_ver = build(0, N - 1);
      |         ^~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5456 KB Output is correct
2 Correct 7 ms 5456 KB Output is correct
3 Correct 5 ms 5456 KB Output is correct
4 Correct 37 ms 15292 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 185816 KB Output is correct
2 Correct 662 ms 185776 KB Output is correct
3 Correct 387 ms 177304 KB Output is correct
4 Correct 2623 ms 66964 KB Output is correct
5 Correct 1303 ms 89236 KB Output is correct
6 Execution timed out 3083 ms 179032 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 185728 KB Output is correct
2 Execution timed out 3051 ms 177652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 9984 KB Output is correct
2 Correct 131 ms 9728 KB Output is correct
3 Correct 207 ms 9728 KB Output is correct
4 Correct 1043 ms 9728 KB Output is correct
5 Correct 917 ms 9984 KB Output is correct
6 Correct 189 ms 8528 KB Output is correct
7 Correct 829 ms 9728 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 7 ms 5456 KB Output is correct
3 Correct 7 ms 5456 KB Output is correct
4 Correct 5 ms 5456 KB Output is correct
5 Correct 37 ms 15292 KB Output is correct
6 Correct 633 ms 185816 KB Output is correct
7 Correct 662 ms 185776 KB Output is correct
8 Correct 387 ms 177304 KB Output is correct
9 Correct 2623 ms 66964 KB Output is correct
10 Correct 1303 ms 89236 KB Output is correct
11 Execution timed out 3083 ms 179032 KB Time limit exceeded
12 Halted 0 ms 0 KB -