oj.uz

Submission #477709

# Submission time Handle Problem Language Result Execution time Memory
477709 2021-10-03T09:02:00 Z InternetPerson10 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 1052 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> pas;
vector<int> heights, m;
set<int> ses[100001];
set<int> savs[400001];
vector<vector<int>> upd;

int n;

void init(int N, int D, int H[]) {
    n = N;
    pas.resize(n);
    heights.resize(n);
    m.resize(n);
    upd.resize(n);
    for(int i = 0; i < n; i++) {
        pas[i].first = H[i];
        pas[i].second = i;
        ses[i] = set<int>();
    }
    sort(pas.begin(), pas.end());
    for(int i = 0; i < n; i++) {
        m[pas[i].second] = i;
        heights[i] = pas[i].first;
    }
    for(int i = 0; i < n; i++) {
        upd[i].push_back(-1);
    }
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; i++) {
        int x = A[i], y = B[i];
        x = m[x]; y = m[y];
        auto it1 = ses[x].find(y);
        if(it1 == ses[x].end()) {
            ses[x].insert(y);
            ses[y].insert(x);
        }
        else {
            ses[x].erase(y);
            ses[y].erase(x);
        }
        upd[x].push_back(2*i);
        upd[y].push_back(2*i+1);
        savs[2*i] = ses[x];
        savs[2*i+1] = ses[y];
    }
}

int question(int x, int y, int v) {
    v--;
    x = m[x]; y = m[y];
    int ans = 1000000000;
    auto itxx = upper_bound(upd[x].begin(), upd[x].end(), 2*v+1);
    itxx--;
    auto ityy = upper_bound(upd[y].begin(), upd[y].end(), 2*v+1);
    ityy--;
    if(*ityy == -1 || *itxx == -1) return ans;
    set<int> sx = savs[*itxx]; 
    set<int> sy = savs[*ityy]; 
    auto itx = sx.begin();
    auto ity = sy.begin();
    while(itx != sx.end() && ity != sy.end()) {
        ans = min(ans, abs(heights[*itx] - heights[*ity]));
        if(heights[*itx] < heights[*ity]) itx++;
        else if(heights[*itx] > heights[*ity]) ity++;
        else {
            return 0;
        }
    }
    return ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24136 KB Output is correct
2 Correct 17 ms 24136 KB Output is correct
3 Correct 14 ms 24144 KB Output is correct
4 Correct 43 ms 31504 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 109704 KB Output is correct
2 Correct 586 ms 109772 KB Output is correct
3 Correct 556 ms 212912 KB Output is correct
4 Runtime error 753 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 109940 KB Output is correct
2 Runtime error 486 ms 262148 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 27432 KB Output is correct
2 Correct 120 ms 32796 KB Output is correct
3 Correct 170 ms 33728 KB Output is correct
4 Correct 1052 ms 88480 KB Output is correct
5 Correct 943 ms 72464 KB Output is correct
6 Correct 220 ms 34996 KB Output is correct
7 Correct 832 ms 78596 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23752 KB Output is correct
2 Correct 16 ms 24136 KB Output is correct
3 Correct 17 ms 24136 KB Output is correct
4 Correct 14 ms 24144 KB Output is correct
5 Correct 43 ms 31504 KB Output is correct
6 Correct 614 ms 109704 KB Output is correct
7 Correct 586 ms 109772 KB Output is correct
8 Correct 556 ms 212912 KB Output is correct
9 Runtime error 753 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -