Submission #1028242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028242		Dennis_Jason	Fountain (eJOI20_fountain)	C++14	100 / 100	489 ms	65804 KiB

fountain

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