oj.uz

Submission #464460

# Submission time Handle Problem Language Result Execution time Memory
464460 2021-08-13T08:54:16 Z SamAnd Fountain (eJOI20_fountain) C++17
100 / 100
 292 ms 29728 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 24244 KB Output is correct
2 Correct 198 ms 22648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 200 ms 24244 KB Output is correct
9 Correct 198 ms 22648 KB Output is correct
10 Correct 3 ms 2892 KB Output is correct
11 Correct 93 ms 14984 KB Output is correct
12 Correct 292 ms 29728 KB Output is correct
13 Correct 210 ms 25332 KB Output is correct
14 Correct 178 ms 23908 KB Output is correct
15 Correct 129 ms 22780 KB Output is correct