oj.uz

Submission #547660

# Submission time Handle Problem Language Result Execution time Memory
547660 2022-04-11T08:33:12 Z tengiz05 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 1139 ms 262144 KB 
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

/*


6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14


*/

namespace sOlUTiON {
    constexpr int N = 1E5, M = 2E5;
    int n, D;
    int h[N];
    vector<int> f[N];
    vector<vector<int>> a[N], con[N];
};
using namespace sOlUTiON;

void init(int _N, int _D, int H[]) {
    n = _N;
    D = _D;
    for (int i = 0; i < n; i++) {
        con[i].push_back({});
        a[i].push_back({});
        f[i].push_back(0);
        h[i] = H[i];
    }
}

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        int u = A[i];
        int v = B[i];
        
        {
            vector<int> b = a[u].back(), c = con[u].back(), w;
            int j = 0;
            while (j < int(b.size()) && b[j] < h[v])
                w.push_back(b[j++]);
            
            auto p = find(c.begin(), c.end(), v);
            if (p != c.end()) {
                j++;
                c.erase(p);
            } else {
                c.push_back(v);
                w.push_back(h[v]);
            }
            
            while (j < int(b.size()))
                w.push_back(b[j++]);
            
            a[u].push_back(w);
            con[u].push_back(c);
        }
        {
            vector<int> b = a[v].back(), c = con[v].back(), w;
            int j = 0;
            while (j < int(b.size()) && b[j] < h[u])
                w.push_back(b[j++]);
            
            auto p = find(c.begin(), c.end(), u);
            if (p != c.end()) {
                j++;
                c.erase(p);
            } else {
                c.push_back(u);
                w.push_back(h[u]);
            }
            
            while (j < int(b.size()))
                w.push_back(b[j++]);
            
            a[v].push_back(w);
            con[v].push_back(c);
        }
        
        f[u].push_back(i + 1);
        f[v].push_back(i + 1);
        assert(con[u].back().size() <= D);
        assert(con[v].back().size() <= D);
    }
}

int question(int x, int y, int v) {
    int p1 = upper_bound(f[x].begin(), f[x].end(), v) - f[x].begin() - 1;
    int p2 = upper_bound(f[y].begin(), f[y].end(), v) - f[y].begin() - 1;
    
    int ans = 1E9;
    
    for (int i = 0; i < int(a[x][p1].size()); i++) {
        for (int j = 0; j < int(a[y][p2].size()); j++) {
            ans = min(ans, abs(a[x][p1][i] - a[y][p2][j]));
        }
    }
    
    return ans;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from potion.cpp:1:
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:102:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         assert(con[u].back().size() <= D);
      |                ~~~~~~~~~~~~~~~~~~~~~^~~~
potion.cpp:103:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |         assert(con[v].back().size() <= D);
      |                ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7724 KB Output is correct
2 Correct 5 ms 7632 KB Output is correct
3 Correct 6 ms 7632 KB Output is correct
4 Correct 34 ms 17688 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 73312 KB Output is correct
2 Correct 543 ms 73356 KB Output is correct
3 Correct 413 ms 81108 KB Output is correct
4 Runtime error 397 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 73288 KB Output is correct
2 Runtime error 384 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11088 KB Output is correct
2 Correct 49 ms 11856 KB Output is correct
3 Correct 78 ms 11976 KB Output is correct
4 Correct 1048 ms 20936 KB Output is correct
5 Correct 1139 ms 18468 KB Output is correct
6 Correct 61 ms 11216 KB Output is correct
7 Correct 610 ms 19308 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7248 KB Output is correct
2 Correct 6 ms 7724 KB Output is correct
3 Correct 5 ms 7632 KB Output is correct
4 Correct 6 ms 7632 KB Output is correct
5 Correct 34 ms 17688 KB Output is correct
6 Correct 639 ms 73312 KB Output is correct
7 Correct 543 ms 73356 KB Output is correct
8 Correct 413 ms 81108 KB Output is correct
9 Runtime error 397 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -