oj.uz

Submission #670003

# Submission time Handle Problem Language Result Execution time Memory
670003 2022-12-07T18:05:28 Z dozer The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 3000 ms 42580 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
#define LOGN 18
#define C 500

vector<vector<int>> curr[100005];
vector<array<int, 3>> moves[100005];
int arr[100005], n;

void init(int N, int D, int H[]) {
    n = N;
    for (int i = 0; i < N; i++)
    {
        vector<int> tmp;
        curr[i].pb(tmp);
        arr[i] = H[i];
    }
}

void curseChanges(int U, int A[], int B[]) {
    set<int> flag[n + 5];
    int cnt[n + 5];
    for (int i = 0; i < U; i++)
    {
        int x = A[i], y= B[i];
        cnt[x]++;
        cnt[y]++;
        if (flag[x].count(y)) flag[x].erase(y);
        else flag[x].insert(y);

        if (flag[y].count(x)) flag[y].erase(x);
        else flag[y].insert(x);

        if (cnt[x] == C)
        {
            vector<int> tmp(flag[x].begin(), flag[x].end());
            curr[x].pb(tmp);
            cnt[x] = 0;
        }

        if (cnt[y] == C)
        {
            vector<int> tmp(flag[y].begin(), flag[y].end());
            curr[y].pb(tmp);
            cnt[y] = 0;
        }

        moves[x].pb({y, i, (int)flag[x].count(y)});
        moves[y].pb({x, i, (int)flag[y].count(x)});
    }
}

int question(int x, int y, int v) {
    int a = 0, b = 0;
    if (moves[x].empty() || moves[y].empty()) return 1e9;

    for (int i = LOGN; i >= 0; i--)
    {
        int tmp1 = a + (1<<i), tmp2 = b + (1<<i);
        if (tmp1 < moves[x].size() && moves[x][tmp1][1] < v) a = tmp1;
        if (tmp2 < moves[y].size() && moves[y][tmp2][1] < v) b = tmp2;
    }

    if (moves[x][a][1] >= v || moves[y][b][1] >= v) return 1e9;

    set<int> aa, bb;
    for (auto i : curr[x][a / C]) aa.insert(i);
    for (auto i : curr[y][b / C]) bb.insert(i);

    int basea = (a / C) * C, baseb = (b / C) * C;
    for (int i = basea; i <= a; i++)
    {
        int curr = moves[x][i][0], flag = moves[x][i][2];
        if (flag) aa.insert(curr);
        else aa.erase(curr);
    }
    for (int i = baseb; i <= b; i++)
    {
        int curr = moves[y][i][0], flag = moves[y][i][2];
        if (flag) bb.insert(curr);
        else bb.erase(curr);
    }

    int i = 0, j = 0;
    int ans = 1e9;
    vector<int> k, l;
    for (auto i : aa) k.pb(arr[i]);
    for (auto i : bb) l.pb(arr[i]);
    sort(k.begin(), k.end());
    sort(l.begin(), l.end());

    while(i < k.size() && j < l.size())
    {
        ans = min(ans, abs(k[i] - l[j]));
        if (k[i] < l[j]) i++;
        else j++;
    }
    return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (tmp1 < moves[x].size() && moves[x][tmp1][1] < v) a = tmp1;
      |             ~~~~~^~~~~~~~~~~~~~~~~
potion.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if (tmp2 < moves[y].size() && moves[y][tmp2][1] < v) b = tmp2;
      |             ~~~~~^~~~~~~~~~~~~~~~~
potion.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     while(i < k.size() && j < l.size())
      |           ~~^~~~~~~~~~
potion.cpp:100:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     while(i < k.size() && j < l.size())
      |                           ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 22 ms 14092 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 42580 KB Output is correct
2 Correct 334 ms 42460 KB Output is correct
3 Correct 1561 ms 21240 KB Output is correct
4 Execution timed out 3058 ms 22040 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 42568 KB Output is correct
2 Execution timed out 3053 ms 22464 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7248 KB Output is correct
2 Correct 226 ms 6320 KB Output is correct
3 Correct 1301 ms 6224 KB Output is correct
4 Correct 2569 ms 6824 KB Output is correct
5 Correct 2086 ms 7120 KB Output is correct
6 Correct 182 ms 6352 KB Output is correct
7 Correct 2762 ms 6520 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 3 ms 5244 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 22 ms 14092 KB Output is correct
6 Correct 355 ms 42580 KB Output is correct
7 Correct 334 ms 42460 KB Output is correct
8 Correct 1561 ms 21240 KB Output is correct
9 Execution timed out 3058 ms 22040 KB Time limit exceeded
10 Halted 0 ms 0 KB -