Submission #547662

#	Time	Username	Problem	Language	Result	Execution time	Memory
547662		tengiz05	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3097 ms	262144 KiB

potion

#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];
};
using namespace sOlUTiON;

void init(int _N, int _D, int H[]) {
    n = _N;
    D = _D;
    for (int i = 0; i < n; i++) {
        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(), w;
            int j = 0;
            while (j < int(b.size()) && (b[j] != v && h[b[j]] <= h[v]))
                w.push_back(b[j++]);
            
            if (j < int(b.size()) && b[j] == v) {
                j++;
            } else {
                w.push_back(v);
            }
            
            while (j < int(b.size()))
                w.push_back(b[j++]);
            
            a[u].push_back(w);
        }
        {
            vector<int> &b = a[v].back(), w;
            int j = 0;
            while (j < int(b.size()) && (b[j] != u && h[b[j]] <= h[u]))
                w.push_back(b[j++]);
            
            if (j < int(b.size()) && b[j] == u) {
                j++;
            } else {
                w.push_back(u);
            }
            
            while (j < int(b.size()))
                w.push_back(b[j++]);
            
            a[v].push_back(w);
        }
        
        f[u].push_back(i + 1);
        f[v].push_back(i + 1);
    }
}

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(h[a[x][p1][i]] - h[a[y][p2][j]]));
        }
    }
    
    return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30