oj.uz

답안 #464456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464456 2021-08-13T08:53:18 Z SamAnd Fountain (eJOI20_fountain) C++17
30 / 100
 204 ms 27148 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

int n, qq;
int d[N], c[N];

int p0[N];

vector<int> g[N];

const int m = 18;
int p[N][m];
int s[N][m];

void dfs(int x)
{
    p[x][0] = p0[x];
    s[x][0] = c[x];
    for (int i = 1; i < m; ++i)
    {
        p[x][i] = p[p[x][i - 1]][i - 1];
        s[x][i] = s[x][i - 1] + s[p[x][i - 1]][i - 1];
    }

    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs(h);
    }
}

int qry(int x, int v)
{
    for (int i = m - 1; i >= 0; --i)
    {
        if (s[x][i] < v)
        {
            v -= s[x][i];
            x = p[x][i];
        }
    }
    return x;
}

void solv()
{
    cin >> n >> qq;
    for (int i = 1; i <= n; ++i)
        cin >> d[i] >> c[i];

    stack<int> s;
    for (int i = n; i >= 1; --i)
    {
        while (!s.empty() && d[i] > d[s.top()])
            s.pop();
        if (s.empty())
            p0[i] = 0;
        else
            p0[i] = s.top();
        s.push(i);
    }

    for (int x = 1; x <= n; ++x)
        g[p0[x]].push_back(x);
    dfs(0);

    while (qq--)
    {
        int x, v;
        cin >> x >> v;
        cout << qry(x, v) << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message

fountain.cpp: In function 'void dfs(int)':
fountain.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 27148 KB Output is correct
2 Correct 204 ms 25812 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Halted 0 ms 0 KB -