oj.uz

Submission #963486

# Submission time Handle Problem Language Result Execution time Memory
963486 2024-04-15T06:58:51 Z Ghetto The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 68692 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, K = 100, 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<set<int>> crit_adj[MAX_N];
void update1(int u, int v) { // one-way
    if (adj[u].count(v)) adj[u].erase(v);
    else adj[u].insert(v);
}
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});
                crit_adj[u].push_back(adj[u]);
            }
            continue;
        }

        int u = id[e1[upd]], v = id[e2[upd]];
        update1(u, v);
        update1(v, u);
        upds[u].push_back({upd, v});
        upds[v].push_back({upd, u});

        if (((int) upds[u].size() - 1) % K == 0) crit_adj[u].push_back(adj[u]);
        if (((int) upds[v].size() - 1) % K == 0) crit_adj[v].push_back(adj[v]);
    }

    // for (int i = 0; i < n; i++) {
    //     cout << i << ": ";
    //     for (pii el : upds[i])
    //         cout << el.first << " " << el.second << ",";
    //     cout << endl;
    // }

}

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();
}

void update2(int u, int upd) { // Makes adj[u] what it should be
    int hi = upper_bound(upds[u].begin(), upds[u].end(), make_pair(upd, (int) 1e9)) - upds[u].begin() - 1; // First update with time <= upd
    int lo = K * (hi / K);
    adj[u] = crit_adj[u][hi / K];    

    for (int i = lo + 1; i <= hi; i++) 
        update1(u, upds[u][i].second);
}
int question(int u, int v, int upd) {
    u = id[u]; v = id[v];

    update2(u, upd);
    update2(v, upd);

    int ans = 1e9;
    auto l_it = adj[v].begin(), r_it = adj[v].begin();
    for (auto it = adj[u].begin(); it != adj[u].end(); it++) {
        while (l_it != adj[v].end() && next(l_it, 1) != adj[v].end() && h[rev_id[*next(l_it, 1)]] <= h[rev_id[*it]]) l_it++;
        while (r_it != adj[v].end() && h[rev_id[*r_it]] <= h[rev_id[*it]]) r_it++;

        if (l_it != adj[v].end()) ans = min(ans, abs(h[rev_id[*it]] - h[rev_id[*l_it]]));
        if (r_it != adj[v].end()) ans = min(ans, abs(h[rev_id[*it]] - h[rev_id[*r_it]]));
    }    
    return ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 49856 KB Output is correct
2 Correct 366 ms 49736 KB Output is correct
3 Correct 411 ms 30492 KB Output is correct
4 Correct 2938 ms 50756 KB Output is correct
5 Correct 1043 ms 39052 KB Output is correct
6 Execution timed out 3031 ms 68692 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 49684 KB Output is correct
2 Correct 2487 ms 67864 KB Output is correct
3 Correct 2144 ms 51904 KB Output is correct
4 Execution timed out 3061 ms 68436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13488 KB Output is correct
2 Correct 216 ms 12668 KB Output is correct
3 Correct 393 ms 13156 KB Output is correct
4 Correct 1226 ms 13656 KB Output is correct
5 Correct 1054 ms 13656 KB Output is correct
6 Correct 172 ms 12384 KB Output is correct
7 Correct 959 ms 13656 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 36 ms 22116 KB Output is correct
6 Correct 361 ms 49856 KB Output is correct
7 Correct 366 ms 49736 KB Output is correct
8 Correct 411 ms 30492 KB Output is correct
9 Correct 2938 ms 50756 KB Output is correct
10 Correct 1043 ms 39052 KB Output is correct
11 Execution timed out 3031 ms 68692 KB Time limit exceeded
12 Halted 0 ms 0 KB -