oj.uz

Submission #849239

# Submission time Handle Problem Language Result Execution time Memory
849239 2023-09-14T09:47:24 Z faruk The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 47580 KB 
#include <bits/stdc++.h>    	
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<int, int> pii;

const int C = 80;
const int MAXN = 1e5+1;
const int MAXU = 2e5+1;

int n, d, u;
vector<int> heights(MAXN);
vector<pii> changes(MAXU);

int min_dist(vector<int> first, vector<int> second) {
    if (first.empty() || second.empty())
        return 1e9;
    for (int i = 0; i < first.size(); i++)
        first[i] = heights[first[i]];
    for (int i = 0; i <second.size(); i++)
        second[i] = heights[second[i]];
    sort(all(first));
    sort(all(second));

    int pnt1 = 0, pnt2 = 0, out = 2e9;
    while (pnt1 < first.size() and pnt2 < second.size()) {
        out = min(out, abs(first[pnt1] - second[pnt2]));

        if (pnt1 + 1 == first.size())
            pnt2++;
        else if (pnt2 + 1 == second.size())
            pnt1++;
        else if (first[pnt1] < second[pnt2])
            pnt1++;
        else
            pnt2++;
    }
    return out;
}

vector<int> state_tim[MAXN];
vector<vector<int> > state_set[MAXN];
vector<pii> individ_updates[MAXN];
void init(int N, int D, int H[]) {
    n = N;
    for (int i = 0; i < n; i++)
    {
        heights[i] = H[i];
        state_tim[i].push_back(-1);
        state_set[i].push_back(vector<int>());
    }
    d = D;
}

void process(set<int> &set, int &val) {
    if (set.count(val))
        set.erase(val);
    else
        set.insert(val);
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; i++)
    {
        changes[i].first = A[i], changes[i].second = B[i];
        individ_updates[A[i]].push_back({i, B[i]});
        individ_updates[B[i]].push_back({i, A[i]});
    }
    
    vector<int> time_since_last(n, 0);
    vector<set<int> > guys(n);
    for (int i = 0; i < u; i++) {
        int a = changes[i].first, b = changes[i].second;
        process(guys[a], b);
        process(guys[b], a);
        if (time_since_last[a] == C) {
            state_tim[a].push_back(i);
            state_set[a].push_back(vector<int>(all(guys[a])));
            time_since_last[a] = 0;
        }
        if (time_since_last[b] == C) {
            state_tim[b].push_back(i);
            state_set[b].push_back(vector<int>(all(guys[b])));
            time_since_last[b] = 0;
        }
        time_since_last[a]++;
        time_since_last[b]++;
    }
}

vector<int> get_set(int x, int v) {
    int check_tim_idx = upper_bound(all(state_tim[x]), v) - state_tim[x].begin() - 1;
    set<int> guys(all(state_set[x][check_tim_idx]));
    int idx = lower_bound(all(individ_updates[x]), 
        pii(state_tim[x][check_tim_idx], 1e9)) - individ_updates[x].begin();
    
    for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
        process(guys, individ_updates[x][idx].second);
    return vector<int>(all(guys));
}

int question(int x, int y, int v) {
    vector<int> x_set = get_set(x, v), y_set = get_set(y, v);
    return min_dist(x_set, y_set);
}

Compilation message

potion.cpp: In function 'int min_dist(std::vector<int>, std::vector<int>)':
potion.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < first.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i <second.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |            ~~~~~^~~~~~~~~~~~~~
potion.cpp:27:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |                                    ~~~~~^~~~~~~~~~~~~~~
potion.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (pnt1 + 1 == first.size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~
potion.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         else if (pnt2 + 1 == second.size())
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> get_set(int, int)':
potion.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9724 KB Output is correct
2 Correct 5 ms 9560 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 22 ms 21328 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 47324 KB Output is correct
2 Correct 294 ms 47532 KB Output is correct
3 Correct 378 ms 26812 KB Output is correct
4 Correct 2468 ms 27244 KB Output is correct
5 Correct 752 ms 36128 KB Output is correct
6 Execution timed out 3009 ms 37212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 47580 KB Output is correct
2 Execution timed out 3041 ms 31580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11988 KB Output is correct
2 Correct 205 ms 10944 KB Output is correct
3 Incorrect 38 ms 10972 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9304 KB Output is correct
2 Correct 4 ms 9724 KB Output is correct
3 Correct 5 ms 9560 KB Output is correct
4 Correct 5 ms 9816 KB Output is correct
5 Correct 22 ms 21328 KB Output is correct
6 Correct 275 ms 47324 KB Output is correct
7 Correct 294 ms 47532 KB Output is correct
8 Correct 378 ms 26812 KB Output is correct
9 Correct 2468 ms 27244 KB Output is correct
10 Correct 752 ms 36128 KB Output is correct
11 Execution timed out 3009 ms 37212 KB Time limit exceeded
12 Halted 0 ms 0 KB -