oj.uz

Submission #689912

# Submission time Handle Problem Language Result Execution time Memory
689912 2023-01-29T17:55:46 Z vjudge1 Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 15040 KB 
#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, ll>
#define oo 1e9

using namespace std;

int n;
vector<ll> capacity, diameter;

vector<vector<int>> st;
vector<int> LOGS;

vector<int> after;

void build(){
    LOGS.resize(n + 1);
    LOGS[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        LOGS[i] = LOGS[i / 2] + 1;
    }
    

    int MaxLog = 0;
    int a = n;
    while(a > 0){
        a >>= 1;
        MaxLog++;
    }
    
    st.resize(MaxLog, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        st[0][i] = diameter[i];
    }
    
    for (int j = 1; j < MaxLog; j++)
    {
        for (int i = 0; i <= n - (1 << j); i++)
        {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int ask(int l, int r){
    int d = r - l + 1;
    int j = LOGS[d];
    return max(st[j][l], st[j][r - (1 << j) + 1]);
}

int main(){
    int q;
    cin >> n >> q;
    n += 1;
    capacity.resize(n + 1);
    diameter.resize(n + 1);
    after.resize(n + 1);
    for (int i = 1; i < n; i++)
    {
        cin >> diameter[i] >> capacity[i];
    }
    diameter[n] = oo * 2;
    capacity[n] = 1e18;

    build();

    vector<int> inputCount(n + 1);
    for (int i = 1; i < n; i++)
    {
        int l = i, r = n;
        while(l < r){
            int mid = (l + r) / 2;
            if(ask(l, mid) > diameter[i]){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        after[i] = r;
        inputCount[r]++;
    }
    after[n] = 0;
    vector<int> startPoints;
    for (int i = 1; i <= n; i++)
    {
        if(inputCount[i] != 1){
            startPoints.emplace_back(i);
        }
    }
    int mp[n + 1][2];
    vector<vector<pii>> chains;
    for(int point:startPoints){
        chains.push_back({{0, 0}, {point, capacity[point]}});
        
        mp[point][0] = chains.size() - 1;
        mp[point][1] = 1;

        vector<pii> &lastChain = chains[chains.size() - 1];
        
        point = after[point];
        while(point != 0 && (*lower_bound(startPoints.begin(), startPoints.end(), point)) != point){
            lastChain.push_back({point, lastChain[lastChain.size() - 1].second + capacity[point]});
            mp[point][0] = chains.size() - 1;
            mp[point][1] = lastChain.size() - 1;
            point = after[point];
        }
    }
    
    while(q--){
        ll j, v; cin >> j >> v;
        pii ans = {0, 0};
        while(v > 0){
            vector<pii> &chain = chains[mp[j][0]];
            ans = chain[chain.size() - 1];
            int l = mp[j][1], r = chain.size() - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(chain[mid].second - chain[mp[j][1] - 1].second >= v){
                    ans = chain[mid];
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            v -= ans.second - chain[mp[j][1] - 1].second;
            //cout << v << ' ' << ans.first << '\n'; 

            if(v > 0) j = after[ans.first];
        }
        if(ans.first == n) ans.first = 0;
        cout << ans.first << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 13276 KB Output is correct
2 Correct 350 ms 15040 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 321 ms 13276 KB Output is correct
9 Correct 350 ms 15040 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Execution timed out 1588 ms 10420 KB Time limit exceeded
12 Halted 0 ms 0 KB -