oj.uz

Submission #1028218

# Submission time Handle Problem Language Result Execution time Memory
1028218 2024-07-19T15:21:43 Z Dennis_Jason Fountain (eJOI20_fountain) C++14
60 / 100
 526 ms 65268 KB 
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 100001
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
int n,q;
const int L=30;
/*
 * 1: 4 10                    tree
   2: 6 8                       7
   3: 3 5                     5   6
   4: 4 14                  2  4
   5: 10 9                 1     3
   6: 4 20
 *
 */
vector<vector<int>>G(NMAX);
int dim[NMAX],cap[NMAX];
int tata[NMAX][L],vol[NMAX][L];
void dfs(int node,int parent)
{
    tata[node][0]=parent;
    vol[node][0]=cap[parent];
    for(auto x:G[node])
    {
        if(x!=parent)
            dfs(x,node);
    }
}
void precompute()
{
    for(int j=1;j<=20;++j)
    {
        for(int i=1;i<=n+1;++i)
        {
            if(tata[i][j-1]!=-1)
            {
                tata[i][j]=tata[tata[i][j-1]][j-1];
                vol[i][j]=vol[tata[i][j-1]][j-1]+vol[i][j-1];
            }
        }
    }
}

int binary_lift(int node,int l)
{
    l-=cap[node];
    for(int i=20;i>=0;--i)
    {
        if(tata[node][i]==-1)
            continue;
        if(vol[node][i]<l) {
            l -= vol[node][i];
            node = tata[node][i];
        }
    }
    return tata[node][0];
}
signed main() {

    cin>>n>>q;
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;
        dim[i]=x;
        cap[i]=y;
    }
    cap[n+1]=2000000000;
    stack<pii> s;
    s.push({INT_MAX, n+1});
    for(int i=n;i>=1;--i)
    {
        while(s.top().first<=dim[i])
            s.pop();
        G[i].pb(s.top().second);
        G[s.top().second].pb(i);
        s.push({dim[i],i});
    }
    memset(tata,-1,sizeof(tata));
    dfs(n+1,0);
    precompute();
    for(int i=1;i<=q;++i)
    {
        int x,y;
        cin>>x>>y;
        if(y<=cap[x])
        {
            cout<<x<<nl;
        }
        else
        {
            int ans= binary_lift(x,y);
            if(ans==n+1)
                cout<<0<<nl;
            else
                cout<<ans<<nl;
        }
    }


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 7 ms 27484 KB Output is correct
3 Correct 8 ms 27476 KB Output is correct
4 Correct 9 ms 27736 KB Output is correct
5 Correct 10 ms 27736 KB Output is correct
6 Correct 12 ms 27732 KB Output is correct
7 Correct 11 ms 27736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 63056 KB Output is correct
2 Correct 363 ms 60844 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 7 ms 27484 KB Output is correct
3 Correct 8 ms 27476 KB Output is correct
4 Correct 9 ms 27736 KB Output is correct
5 Correct 10 ms 27736 KB Output is correct
6 Correct 12 ms 27732 KB Output is correct
7 Correct 11 ms 27736 KB Output is correct
8 Correct 346 ms 63056 KB Output is correct
9 Correct 363 ms 60844 KB Output is correct
10 Correct 9 ms 27740 KB Output is correct
11 Correct 207 ms 45416 KB Output is correct
12 Incorrect 526 ms 65268 KB Output isn't correct
13 Halted 0 ms 0 KB -