oj.uz

Submission #1024820

# Submission time Handle Problem Language Result Execution time Memory
1024820 2024-07-16T10:43:38 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 112 ms 37536 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> G[100005];
int n, q;
int dijametar[100005], kapacitet[100005];
int parent[100005][30], sobira[100005][30];

void dfs(int teme, int preth) {
    parent[teme][0]=preth;
    sobira[teme][0]=kapacitet[preth];
    for (auto next:G[teme]) {
        if (next!=preth)
            dfs(next, teme);
    }
}

void precomputeSparseMatrix() {
    for (int i=1;i<20;i++) {
        for (int teme=1;teme<=n+1;teme++) {
            if (parent[teme][i-1]!=-1) {
                parent[teme][i]=parent[parent[teme][i-1]][i-1];
                sobira[teme][i]=sobira[parent[teme][i-1]][i-1]+sobira[teme][i-1];
            }
        }
    }
}

int binary_lifting(int rezervoar, int voda) {
    voda-=kapacitet[rezervoar];
    for (int i=20;i>=0;i--) {
        if (parent[rezervoar][i]==-1) continue;
        //cout << "i=" << i << " parent=" << parent[rezervoar][i] << " " << sobira[rezervoar][i]+kapacitet[parent[rezervoar][i]] << endl;
        if (sobira[rezervoar][i]<voda) {
            voda-=sobira[rezervoar][i];
            rezervoar=parent[rezervoar][i];
        }
        //cout << "sega rezervoar=" << rezervoar << endl;
    }
    return parent[rezervoar][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1;i<=n;i++)
        cin >> dijametar[i] >> kapacitet[i];
    kapacitet[n+1]=2000000000;
    stack<pair<int,int> > s;
    s.push({INT_MAX, n+1});
    for (int i=n;i>=1;i--) {
        while (s.top().first<=dijametar[i])
            s.pop();
        G[i].push_back(s.top().second);
        G[s.top().second].push_back(i);
        //cout << "sleden na " << i << " e " << s.top().second << endl;
        s.push({dijametar[i], i});
    }
    memset(parent, -1, sizeof(parent));
    dfs(n+1, 0);
    precomputeSparseMatrix();
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (kapacitet[r]>=v) cout << r << '\n';
        else {
            int rez=binary_lifting(r, v);
            if (rez==n+1) cout << 0 << '\n';
            else cout << rez << '\n';
        }
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16476 KB Output is correct
2 Correct 3 ms 16648 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 34320 KB Output is correct
2 Correct 86 ms 33876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16476 KB Output is correct
2 Correct 3 ms 16648 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 79 ms 34320 KB Output is correct
9 Correct 86 ms 33876 KB Output is correct
10 Correct 3 ms 16728 KB Output is correct
11 Correct 47 ms 27984 KB Output is correct
12 Correct 112 ms 37536 KB Output is correct
13 Correct 109 ms 33972 KB Output is correct
14 Correct 73 ms 33188 KB Output is correct
15 Correct 57 ms 33484 KB Output is correct