oj.uz

Submission #695070

# Submission time Handle Problem Language Result Execution time Memory
695070 2023-02-04T17:19:08 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 435 ms 23116 KB 
#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<int> d;
vector<int> c;
vector<vector<int>> par;
vector<vector<ll>> st;
vector<int> msb;

void build(){
    msb.resize(n + 1, 0);
    for (int i = 2; i <= n; i++)
    {
        msb[i] = msb[i / 2] + 1;
    }
    st.resize(msb[n] + 1, vector<ll>(n + 1));
    par.resize(msb[n] + 1, vector<int>(n + 1));

    stack<int> s;
    s.push(n);
    for (int i = n; i >= 1; i--)
    {
        while(d[s.top()] <= d[i] && i != n){
            s.pop();
        }
        if(i == n){
            par[0][i] = n;
        }
        else{
            par[0][i] = s.top();
        }
        st[0][i] = c[i];
        s.push(i);
    }
    
    for (int j = 1; j <= msb[n]; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
            st[j][i] = st[j - 1][i] + st[j - 1][par[j - 1][i]];
        }
    }
}

int ask(int r, ll v){
    int i = r;

    while(true){
        int j = 0;
        while(j <= msb[n] && v > st[j][i]){
            j++;
        }
        if(j == 0){
            break;
        }
        v -= st[j - 1][i];
        i = par[j - 1][i];
    }
    if(i == n) i = 0;
    return i;
}

int main()
{
    int q;
    cin >> n >> q;
    n++;
    d.resize(n + 1);
    c.resize(n + 1);

    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &d[i], &c[i]);
    }
    d[n] = oo;
    c[n] = oo;

    build();
    while(q--){
        ll r, v; scanf("%lld %lld", &r, &v);
        cout << ask(r, v) << '\n';
    }
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d", &d[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         ll r, v; scanf("%lld %lld", &r, &v);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 21456 KB Output is correct
2 Correct 292 ms 19948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 274 ms 21456 KB Output is correct
9 Correct 292 ms 19948 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 87 ms 12260 KB Output is correct
12 Correct 435 ms 23008 KB Output is correct
13 Correct 256 ms 22944 KB Output is correct
14 Correct 110 ms 22936 KB Output is correct
15 Correct 102 ms 23116 KB Output is correct