oj.uz

Submission #669616

# Submission time Handle Problem Language Result Execution time Memory
669616 2022-12-06T20:54:25 Z dozer The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2087 ms 35820 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
//#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second


vector<pair<pii, int>> curr[100005];
int arr[100005], n;


void init(int N, int D, int H[]) {
    n = N;
    for (int i = 0; i < N; i++)
        arr[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    map<int, int> last[n + 5];
    for (int i = 0; i < U; i++)
    {
        int u = A[i], v = B[i];
        if (last[u][v])
        {
            curr[u].pb({{last[u][v], i + 1}, arr[v]});
            curr[v].pb({{last[u][v], i + 1}, arr[u]});
            last[u][v] = 0;
            last[v][u] = 0;
        }
        else last[u][v] = i + 1, last[v][u] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
        for (auto j : last[i])
        {
            if (j.nd != 0) curr[i].pb({{j.nd, U + 2}, arr[j.st]});
        }
    }
}

int question(int x, int y, int v) {
    vector<int> k, l;
    v++;
    for (auto i : curr[x])
        if (i.st.st < v && i.st.nd >= v) k.pb(i.nd);
    for (auto i : curr[y])
        if (i.st.st < v && i.st.nd >= v) l.pb(i.nd);
    sort(k.begin(), k.end());
    sort(l.begin(), l.end());
    int ans = 1e9;
    int i = 0, j = 0;
    /*
    cout<<x<<" : ";
    for (auto i : k) cout<<i<<sp;
    cout<<endl;
    cout<<y<<" : ";
    for (auto i : l) cout<<i<<sp;
        cout<<endl;*/
    while(i < k.size() && j < l.size())
    {
        int a = k[i], b = l[j];
        ans = min(ans, abs(a - b));
        if (a < b) i++;
        else if (b < a) j++;
        else return ans;
    }
    return ans;

}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:64:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     while(i < k.size() && j < l.size())
      |           ~~^~~~~~~~~~
potion.cpp:64:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     while(i < k.size() && j < l.size())
      |                           ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2768 KB Output is correct
2 Correct 4 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 16 ms 8292 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 35784 KB Output is correct
2 Correct 281 ms 35820 KB Output is correct
3 Correct 327 ms 12620 KB Output is correct
4 Correct 1115 ms 24440 KB Output is correct
5 Correct 429 ms 30760 KB Output is correct
6 Correct 1932 ms 23452 KB Output is correct
7 Correct 369 ms 23220 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 35784 KB Output is correct
2 Correct 1054 ms 17692 KB Output is correct
3 Correct 602 ms 24012 KB Output is correct
4 Correct 948 ms 23452 KB Output is correct
5 Correct 352 ms 35544 KB Output is correct
6 Correct 1016 ms 23300 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4560 KB Output is correct
2 Correct 74 ms 3920 KB Output is correct
3 Correct 130 ms 3476 KB Output is correct
4 Correct 647 ms 4172 KB Output is correct
5 Correct 636 ms 4440 KB Output is correct
6 Correct 78 ms 4076 KB Output is correct
7 Correct 598 ms 3588 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 3 ms 2768 KB Output is correct
3 Correct 4 ms 2768 KB Output is correct
4 Correct 2 ms 2768 KB Output is correct
5 Correct 16 ms 8292 KB Output is correct
6 Correct 293 ms 35784 KB Output is correct
7 Correct 281 ms 35820 KB Output is correct
8 Correct 327 ms 12620 KB Output is correct
9 Correct 1115 ms 24440 KB Output is correct
10 Correct 429 ms 30760 KB Output is correct
11 Correct 1932 ms 23452 KB Output is correct
12 Correct 369 ms 23220 KB Output is correct
13 Correct 247 ms 35784 KB Output is correct
14 Correct 1054 ms 17692 KB Output is correct
15 Correct 602 ms 24012 KB Output is correct
16 Correct 948 ms 23452 KB Output is correct
17 Correct 352 ms 35544 KB Output is correct
18 Correct 1016 ms 23300 KB Output is correct
19 Correct 36 ms 4560 KB Output is correct
20 Correct 74 ms 3920 KB Output is correct
21 Correct 130 ms 3476 KB Output is correct
22 Correct 647 ms 4172 KB Output is correct
23 Correct 636 ms 4440 KB Output is correct
24 Correct 78 ms 4076 KB Output is correct
25 Correct 598 ms 3588 KB Output is correct
26 Correct 606 ms 18992 KB Output is correct
27 Correct 1006 ms 23572 KB Output is correct
28 Correct 1152 ms 31176 KB Output is correct
29 Correct 986 ms 24552 KB Output is correct
30 Correct 2067 ms 23516 KB Output is correct
31 Correct 2087 ms 17612 KB Output is correct
32 Correct 1899 ms 23368 KB Output is correct