Submission #464460

#	Time	Username	Problem	Language	Result	Execution time	Memory
464460		SamAnd	Fountain (eJOI20_fountain)	C++17	100 / 100	292 ms	29728 KiB

fountain

#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 (stderr)

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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40