oj.uz

답안 #670006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670006 2022-12-07T18:08:06 Z dozer The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 3000 ms 42568 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 25

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5200 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 25 ms 14156 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 42552 KB Output is correct
2 Correct 334 ms 42520 KB Output is correct
3 Correct 297 ms 22092 KB Output is correct
4 Correct 2970 ms 30828 KB Output is correct
5 Correct 739 ms 35376 KB Output is correct
6 Execution timed out 3063 ms 39268 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 42568 KB Output is correct
2 Execution timed out 3045 ms 34500 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 7248 KB Output is correct
2 Correct 153 ms 6488 KB Output is correct
3 Correct 270 ms 6488 KB Output is correct
4 Correct 1642 ms 6992 KB Output is correct
5 Correct 1542 ms 7248 KB Output is correct
6 Correct 193 ms 6480 KB Output is correct
7 Correct 1332 ms 6700 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 25 ms 14156 KB Output is correct
6 Correct 341 ms 42552 KB Output is correct
7 Correct 334 ms 42520 KB Output is correct
8 Correct 297 ms 22092 KB Output is correct
9 Correct 2970 ms 30828 KB Output is correct
10 Correct 739 ms 35376 KB Output is correct
11 Execution timed out 3063 ms 39268 KB Time limit exceeded
12 Halted 0 ms 0 KB -