oj.uz

답안 #547939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547939 2022-04-12T03:59:11 Z tengiz05 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 390 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 {
    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];
    vector<int> 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];
    }
}

bit get(vector<int> &a, int x) {
    bit b{};
    for (int i = 0; i < 283; i++) {
        b[i] = a[x * 283 + i];
    }
    return b;
}

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(283 * cnt[i]);
    }
    
    for (int i = 0; i < 50000; i++) cerr << endl;
    
    
    for (int i = 0; i < U; i++) {
        int u = A[i];
        int v = B[i];
        
        {
            vector<int> b, w;
            if (!a[u].empty()) {
                b = decompress(get(a[u], a[u].size() / 283 - 1));
            }
            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++]);
            
            auto x = compress(w);
            for (int i = 0; i < 283; i++) {
                a[u].push_back(x[i]);
            }
        }
        {
            vector<int> b, w;
            if (!a[v].empty()) {
                b = decompress(get(a[v], a[v].size() / 283 - 1));
            }
            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++]);
            
            auto x = compress(w);
            for (int i = 0; i < 283; i++) {
                a[v].push_back(x[i]);
            }
        }
        
        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;
    }
    
    int s1 = a[x][283 * p1 + 282];
    int s2 = a[y][283 * p2 + 282];
    
    if (s1 == 0 || s2 == 0)
        return ans;
    
    vector<int> f = decompress(get(a[x], p1));
    vector<int> s = decompress(get(a[y], p2));
    
    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

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 7240 KB Output is correct
2 Correct 68 ms 7296 KB Output is correct
3 Correct 68 ms 7268 KB Output is correct
4 Correct 78 ms 8468 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 161 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 150 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 27676 KB Output is correct
2 Correct 199 ms 27548 KB Output is correct
3 Correct 205 ms 27588 KB Output is correct
4 Correct 390 ms 27872 KB Output is correct
5 Correct 347 ms 27832 KB Output is correct
6 Correct 213 ms 27460 KB Output is correct
7 Correct 324 ms 27624 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 5052 KB Output is correct
2 Correct 65 ms 7240 KB Output is correct
3 Correct 68 ms 7296 KB Output is correct
4 Correct 68 ms 7268 KB Output is correct
5 Correct 78 ms 8468 KB Output is correct
6 Runtime error 161 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -