제출 #694960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
694960		vjudge1	Fountain (eJOI20_fountain)	C++17	0 / 100	45 ms	41964 KiB

fountain

#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(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("%d %lld", &r, &v);
        cout << ask(r, v) << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

fountain.cpp: In function 'int main()':
fountain.cpp:88:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   88 |         ll r, v; scanf("%d %lld", &r, &v);
      |                         ~^        ~~
      |                          |        |
      |                          int*     long long int*
      |                         %lld
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("%d %lld", &r, &v);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40