oj.uz

Submission #470664

# Submission time Handle Problem Language Result Execution time Memory
470664 2021-09-04T18:59:34 Z Sho10 Fountain (eJOI20_fountain) C++17
100 / 100
 385 ms 47064 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,q,d[100005],c[100005],par[100005][25],sum[100005][25];
ll query(ll &pos,ll &cnt){
for(ll i=20;i>=0;i--)
{
    if(pos==0){
        break;
    }
   // cout<<sum[pos][i]<<' '<<cnt<<' '<<i<<endl;
    if(sum[pos][i]<cnt){
        cnt-=sum[pos][i];
        pos=par[pos][i];
    }
}
return pos;
}
int32_t main(){
CODE_START;
cin>>n>>q;
for(ll i=1;i<=n;i++)
{
    cin>>d[i]>>c[i];
}
stack<ll>s;
d[0]=LINF;
s.push(0);
for(ll i=n;i>=1;i--){
    while(d[s.top()]<=d[i]){
        s.pop();
    }
    par[i][0]=s.top();
    s.push(i);
}
for(ll j=1;j<=20;j++){
for(ll i=n;i>=1;i--)
    par[i][j]=par[par[i][j-1]][j-1];
}
for(ll i=1;i<=n;i++)
{
    sum[i][0]=c[i];
}
for(ll j=1;j<=20;j++)
{
    for(ll i=n;i>=1;i--)
    {
        sum[i][j]=sum[i][j-1]+sum[par[i][j-1]][j-1];
    }
}
while(q--){
ll x,y;
cin>>x>>y;
cout<<query(x,y)<<endl;
}
}

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 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 40540 KB Output is correct
2 Correct 316 ms 40516 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 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 253 ms 40540 KB Output is correct
9 Correct 316 ms 40516 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 140 ms 25216 KB Output is correct
12 Correct 385 ms 47064 KB Output is correct
13 Correct 289 ms 45852 KB Output is correct
14 Correct 235 ms 45080 KB Output is correct
15 Correct 186 ms 45380 KB Output is correct