oj.uz

Submission #467015

# Submission time Handle Problem Language Result Execution time Memory
467015 2021-08-21T10:19:00 Z Theo830 Fountain (eJOI20_fountain) C++17
100 / 100
 413 ms 61252 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
ll an[100005][30];
ll sum[100005][30];
ll d[100005],c[100005];
vector<vll>adj;
void build(ll s,ll p){
    an[s][0] = p;
    if(s-1 != -1){
        sum[s][0] = c[s-1];
    }
    else{
        sum[s][0] = 0;
    }
    f(i,1,30){
        an[s][i] = an[an[s][i-1]][i-1];
        sum[s][i] = sum[s][i-1] + sum[an[s][i-1]][i-1];
    }
    for(auto x:adj[s]){
        if(x != p){
            build(x,s);
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,q;
    cin>>n>>q;
    f(i,0,n){
        cin>>d[i]>>c[i];
    }
    set<ii>ex;
    adj.assign(n+5,vll());
    f(i,0,n){
        auto it = ex.begin();
        set<ii>fkale;
        while(it != ex.end() && (*it).F < d[i]){
            adj[(*it).S].pb(i+1);
            adj[i+1].pb((*it).S);
            fkale.insert((*it));
            it++;
        }
        for(auto x:fkale){
            ex.erase(x);
        }
        ex.insert(ii(d[i],i+1));
    }
    for(auto x:ex){
        adj[0].pb(x.S);
        adj[x.S].pb(0);
    }
    build(0,0);
    while(q--){
        ll cur,v;
        cin>>cur>>v;
        for(ll j = 29;j >= 0;j--){
            if(sum[cur][j] < v){
                v -= sum[cur][j];
                cur = an[cur][j];
            }
        }
        cout<<cur<<"\n";
    }
}
/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 56820 KB Output is correct
2 Correct 337 ms 52548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 286 ms 56820 KB Output is correct
9 Correct 337 ms 52548 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 155 ms 31548 KB Output is correct
12 Correct 413 ms 60152 KB Output is correct
13 Correct 369 ms 56896 KB Output is correct
14 Correct 230 ms 56028 KB Output is correct
15 Correct 227 ms 61252 KB Output is correct