oj.uz

Submission #694958

# Submission time Handle Problem Language Result Execution time Memory
694958 2023-02-04T15:00:47 Z vjudge1 Fountain (eJOI20_fountain) C++17
0 / 100
 526 ms 76332 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]];
            cout << i << ' ' << j << ' ' << par[j][i] << ' ' << st[j][i] << '\n';
        }
    }
}

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

    while(true){
        int j = 0;
        while(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--){
        int r, v; scanf("%d %d", &r, &v);
        cout << ask(r, v) << '\n';
    }
}

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 526 ms 76332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -