oj.uz

답안 #694959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
694959 2023-02-04T15:01:09 Z vjudge1 Fountain (eJOI20_fountain) C++17
0 / 100
 43 ms 41904 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, 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: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:87:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         int r, v; scanf("%d %d", &r, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 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 440 KB Output is correct
5 Runtime error 1 ms 724 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 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 440 KB Output is correct
5 Runtime error 1 ms 724 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -