oj.uz

Submission #963631

# Submission time Handle Problem Language Result Execution time Memory
963631 2024-04-15T12:08:59 Z Ghetto The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2525 ms 47228 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, K = 20, MAX_T = 2e5 + 5;
 
int n;
int h[MAX_N]; // Not id
int t;
int e1[MAX_T], e2[MAX_T]; // Not id
 
int id[MAX_N], rev_id[MAX_N]; 
vector<pii> upds[MAX_N]; // {time, node} and {0, -1}
set<int> adj[MAX_N]; // reused
vector<vector<int>> crit_adjs[MAX_N];
void update1(int u, int v, set<int>& s) { // one-way
    if (s.count(v)) s.erase(v);
    else s.insert(v);
}
void save(int u) {
    vector<int> cur_adj(adj[u].begin(), adj[u].end());
    crit_adjs[u].push_back(cur_adj);
}
void precomp() {
    vector<pii> order;
    for (int i = 0; i < n; i++) order.push_back({h[i], i});
    sort(order.begin(), order.end());
    for (int i = 0; i < n; i++) {
        id[order[i].second] = i;
        rev_id[i] = order[i].second;
    }
 
    for (int upd = 0; upd <= t; upd++) {
        if (upd == 0) {
            for (int u = 0; u < n; u++) {
                upds[u].push_back({0, -1});
                save(u);
            }
            continue;
        }
 
        int u = id[e1[upd]], v = id[e2[upd]];
        update1(u, v, adj[u]);
        update1(v, u, adj[v]);
        upds[u].push_back({upd, v});
        upds[v].push_back({upd, u});
 
        if (((int) upds[u].size() - 1) % K == 0) save(u);
        if (((int) upds[v].size() - 1) % K == 0) save(v);
    }
}
 
void init(int tmp_n, int tmp_d, int tmp_h[]) {
    n = tmp_n;
    for (int i = 0; i < n; i++) h[i] = tmp_h[i];
}
void curseChanges(int tmp_t, int tmp_e1[], int tmp_e2[]) {
    t = tmp_t;
    for (int i = 1; i <= t; i++) {
        e1[i] = tmp_e1[i - 1];
        e2[i] = tmp_e2[i - 1];
    }
    precomp();
}
 
set<int> update2(int u, int upd) {
    // First update with time <= upd
    int hi = upper_bound(upds[u].begin(), upds[u].end(), make_pair(upd, (int) 1e9)) - upds[u].begin() - 1; 
    int lo = K * (hi / K);
    set<int> cur_adj(crit_adjs[u][hi / K].begin(), crit_adjs[u][hi / K].end());
 
    for (int i = lo + 1; i <= hi; i++) 
        update1(u, upds[u][i].second, cur_adj);
    return cur_adj;
}
int question(int u, int v, int upd) {
    u = id[u]; 
    v = id[v];
 
    set<int> u_adj(update2(u, upd));
    set<int> v_adj(update2(v, upd));   
 
    int ans = 1e9;
    auto u_it = u_adj.begin(), v_it = v_adj.begin();
    while (u_it != u_adj.end() && v_it != v_adj.end()) {
        int u_h = h[rev_id[*u_it]], v_h = h[rev_id[*v_it]];

        ans = min(ans, abs(u_h - v_h));
        if (u_h <= v_h) u_it++;
        else v_it++;
    }
    return ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 4 ms 11096 KB Output is correct
4 Correct 30 ms 18612 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 46628 KB Output is correct
2 Correct 313 ms 46656 KB Output is correct
3 Correct 216 ms 26484 KB Output is correct
4 Correct 1384 ms 38156 KB Output is correct
5 Correct 503 ms 40744 KB Output is correct
6 Correct 2525 ms 46416 KB Output is correct
7 Correct 578 ms 34204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 46532 KB Output is correct
2 Correct 1521 ms 42908 KB Output is correct
3 Correct 1012 ms 39372 KB Output is correct
4 Correct 1650 ms 46280 KB Output is correct
5 Correct 432 ms 47228 KB Output is correct
6 Correct 1798 ms 46408 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12888 KB Output is correct
2 Correct 117 ms 12376 KB Output is correct
3 Correct 166 ms 12204 KB Output is correct
4 Correct 727 ms 12632 KB Output is correct
5 Correct 680 ms 13060 KB Output is correct
6 Correct 124 ms 12120 KB Output is correct
7 Correct 620 ms 12636 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 4 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 4 ms 11096 KB Output is correct
5 Correct 30 ms 18612 KB Output is correct
6 Correct 321 ms 46628 KB Output is correct
7 Correct 313 ms 46656 KB Output is correct
8 Correct 216 ms 26484 KB Output is correct
9 Correct 1384 ms 38156 KB Output is correct
10 Correct 503 ms 40744 KB Output is correct
11 Correct 2525 ms 46416 KB Output is correct
12 Correct 578 ms 34204 KB Output is correct
13 Correct 307 ms 46532 KB Output is correct
14 Correct 1521 ms 42908 KB Output is correct
15 Correct 1012 ms 39372 KB Output is correct
16 Correct 1650 ms 46280 KB Output is correct
17 Correct 432 ms 47228 KB Output is correct
18 Correct 1798 ms 46408 KB Output is correct
19 Correct 37 ms 12888 KB Output is correct
20 Correct 117 ms 12376 KB Output is correct
21 Correct 166 ms 12204 KB Output is correct
22 Correct 727 ms 12632 KB Output is correct
23 Correct 680 ms 13060 KB Output is correct
24 Correct 124 ms 12120 KB Output is correct
25 Correct 620 ms 12636 KB Output is correct
26 Correct 734 ms 32368 KB Output is correct
27 Correct 1196 ms 39172 KB Output is correct
28 Correct 1312 ms 47224 KB Output is correct
29 Correct 1292 ms 38052 KB Output is correct
30 Correct 2461 ms 46212 KB Output is correct
31 Correct 2057 ms 43436 KB Output is correct
32 Correct 2246 ms 46368 KB Output is correct