oj.uz

Submission #547967

# Submission time Handle Problem Language Result Execution time Memory
547967 2022-04-12T05:05:14 Z tengiz05 The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1402 ms 238136 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 {
    using u32 = unsigned int;
    // 282
    using bit = array<u32, 283>;
    constexpr int N = 1E5, M = 2E5;
    int n, D;
    int h[N];
    vector<int> f[N], add[N];
    vector<bit> a[N];
    bit compress(vector<int> &a) {
        int j = 0, k = 0;
        bit res{};
        for (int i = 0; i < int(a.size()); i++) {
            if (j + 18 <= 32) {
                res[k] |= a[i] << j;
                j += 18;
                if (j == 32) {
                    j = 0;
                    k++;
                }
            } else {
                res[k] |= a[i] << j;
                int x = 32 - j;
                j += 18;
                j -= 32;
                k++;
                res[k] |= a[i] >> x;
            }
        }
        res[282] = a.size();
        return res;
    }
    vector<int> decompress(bit a) {
        int n = a[282];
        int j = 0, k = 0;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            if (j + 18 <= 32) {
                ans[i] = a[k] >> j;
                j += 18;
                if (j == 32) {
                    j = 0;
                    k++;
                }
            } else {
                ans[i] |= a[k] >> j;
                int x = 32 - j;
                j += 18;
                j -= 32;
                k++;
                ans[i] |= a[k] << x;
            }
        }
        for (int &x : ans) x &= (1 << 18) - 1;
        return ans;
    }
};
using namespace sOlUTiON;
 
void init(int _N, int _D, int H[]) {
    n = _N;
    D = _D;
    for (int i = 0; i < n; i++) {
        h[i] = H[i];
    }
}

void Add(vector<int> &b, int v) {
    vector<int> 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++]);
    
    b = w;
}

void curseChanges(int U, int A[], int B[]) {
    int cnt[n] {};
    for (int i = 0; i < U; i++) {
        cnt[A[i]]++;
        cnt[B[i]]++;
    }
    
    for (int i = 0; i < n; i++) {
        a[i].reserve(cnt[i] / 2);
    }
    
    for (int i = 0; i < U; i++) {
        int u = A[i];
        int v = B[i];
        
        {
            vector<int> b, w;
            if (add[u].size() % 2 == 0) {
                add[u].push_back(v);
            } else {
                if (!a[u].empty()) {
                    b = decompress(a[u].back());
                }
                Add(b, add[u].back());
                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(compress(w));
                add[u].push_back(v);
            }
        }
        {
            vector<int> b, w;
            if (add[v].size() % 2 == 0) {
                add[v].push_back(u);
            } else {
                if (!a[v].empty()) {
                    b = decompress(a[v].back());
                }
                Add(b, add[v].back());
                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(compress(w));
                add[v].push_back(u);
            }
        }
        
        f[u].push_back(i + 1);
        f[v].push_back(i + 1);
    }
    for (int i = 0; i < n; i++) {
        assert(a[i].size() == a[i].capacity());
    }
}
 
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;
    if (p1 == -1 || p2 == -1) {
        return ans;
    }
    
    vector<int> f, s;
    if (p1 % 2 == 0) {
        if (p1 > 0) {
            f = decompress(a[x][(p1 - 1) / 2]);
        }
        Add(f, add[x][p1]);
    } else {
        f = decompress(a[x][p1 / 2]);
    }
    if (p2 % 2 == 0) {
        if (p2 > 0) {
            s = decompress(a[y][(p2 - 1) / 2]);
        }
        Add(s, add[y][p2]);
    } else {
        s = decompress(a[y][p2 / 2]);
    }
    
    
    int s1 = f.size();
    int s2 = s.size();
    
    if (s1 == 0 || s2 == 0)
        return ans;
    
    int j = 0;
    for (int i = 0; i < s1; i++) {
        int t = h[f[i]];
        while (j + 1 < s2 && h[s[j]] < t)
            j++;
        ans = min(ans, abs(h[f[i]] - h[s[j]]));
    }
    j = 0;
    for (int i = 0; i < s2; i++) {
        int t = h[s[i]];
        while (j + 1 < s1 && h[f[j]] < t)
            j++;
        ans = min(ans, abs(h[s[i]] - h[f[j]]));
    }
    
    return ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8208 KB Output is correct
2 Correct 6 ms 8272 KB Output is correct
3 Correct 6 ms 8272 KB Output is correct
4 Correct 23 ms 8616 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 213548 KB Output is correct
2 Correct 473 ms 213692 KB Output is correct
3 Correct 358 ms 235488 KB Output is correct
4 Correct 1054 ms 236936 KB Output is correct
5 Correct 500 ms 233440 KB Output is correct
6 Correct 1402 ms 213096 KB Output is correct
7 Correct 554 ms 213056 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 213460 KB Output is correct
2 Correct 960 ms 236972 KB Output is correct
3 Correct 708 ms 213208 KB Output is correct
4 Correct 961 ms 213388 KB Output is correct
5 Correct 510 ms 213524 KB Output is correct
6 Correct 1024 ms 213252 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16592 KB Output is correct
2 Correct 94 ms 18840 KB Output is correct
3 Correct 103 ms 18888 KB Output is correct
4 Correct 281 ms 16860 KB Output is correct
5 Correct 228 ms 16860 KB Output is correct
6 Correct 107 ms 18512 KB Output is correct
7 Correct 228 ms 18752 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 6 ms 8208 KB Output is correct
3 Correct 6 ms 8272 KB Output is correct
4 Correct 6 ms 8272 KB Output is correct
5 Correct 23 ms 8616 KB Output is correct
6 Correct 480 ms 213548 KB Output is correct
7 Correct 473 ms 213692 KB Output is correct
8 Correct 358 ms 235488 KB Output is correct
9 Correct 1054 ms 236936 KB Output is correct
10 Correct 500 ms 233440 KB Output is correct
11 Correct 1402 ms 213096 KB Output is correct
12 Correct 554 ms 213056 KB Output is correct
13 Correct 483 ms 213460 KB Output is correct
14 Correct 960 ms 236972 KB Output is correct
15 Correct 708 ms 213208 KB Output is correct
16 Correct 961 ms 213388 KB Output is correct
17 Correct 510 ms 213524 KB Output is correct
18 Correct 1024 ms 213252 KB Output is correct
19 Correct 61 ms 16592 KB Output is correct
20 Correct 94 ms 18840 KB Output is correct
21 Correct 103 ms 18888 KB Output is correct
22 Correct 281 ms 16860 KB Output is correct
23 Correct 228 ms 16860 KB Output is correct
24 Correct 107 ms 18512 KB Output is correct
25 Correct 228 ms 18752 KB Output is correct
26 Correct 637 ms 238136 KB Output is correct
27 Correct 851 ms 213376 KB Output is correct
28 Correct 876 ms 213424 KB Output is correct
29 Correct 924 ms 236976 KB Output is correct
30 Correct 1340 ms 213408 KB Output is correct
31 Correct 1282 ms 237168 KB Output is correct
32 Correct 1343 ms 213336 KB Output is correct