oj.uz

Submission #670007

# Submission time Handle Problem Language Result Execution time Memory
670007 2022-12-07T18:08:59 Z dozer The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 3000 ms 53960 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 10

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 2 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 4 ms 5200 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 29 ms 14064 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 42564 KB Output is correct
2 Correct 341 ms 42792 KB Output is correct
3 Correct 261 ms 23756 KB Output is correct
4 Execution timed out 3053 ms 43708 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 42612 KB Output is correct
2 Execution timed out 3055 ms 53960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7248 KB Output is correct
2 Correct 125 ms 6512 KB Output is correct
3 Correct 215 ms 6464 KB Output is correct
4 Correct 1542 ms 7360 KB Output is correct
5 Correct 1482 ms 7488 KB Output is correct
6 Correct 166 ms 6544 KB Output is correct
7 Correct 1206 ms 6864 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct
5 Correct 29 ms 14064 KB Output is correct
6 Correct 362 ms 42564 KB Output is correct
7 Correct 341 ms 42792 KB Output is correct
8 Correct 261 ms 23756 KB Output is correct
9 Execution timed out 3053 ms 43708 KB Time limit exceeded
10 Halted 0 ms 0 KB -