oj.uz

Submission #456360

# Submission time Handle Problem Language Result Execution time Memory
456360 2021-08-06T14:13:01 Z DobromirAngelov Fountain (eJOI20_fountain) C++14
100 / 100
 296 ms 22144 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct rez
{
    int d,v;
};
struct torez
{
    int nom,v;
};
int n,q;
rez a[100005];
int logN;
torez spt[100005][20];
void getLog()
{
    int i=0;
    while((1<<i)<n)i++;
    if((1<<i)==n)logN=i;
    logN=i-1;
}
void make_SpTable()
{
    stack<int>st;
    for(int i=n;i>0;i--)
    {
        while(!st.empty()&&a[st.top()].d<=a[i].d)st.pop();
        if(st.empty())
        {
            st.push(i);
            spt[i][0].nom=0;
            spt[i][0].v=a[i].v;
            continue;
        }
        spt[i][0].nom=st.top();
        spt[i][0].v=a[i].v;
        st.push(i);
    }
    for(int j=1;j<=logN;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(spt[i][j-1].nom)spt[i][j].nom=spt[spt[i][j-1].nom][j-1].nom;
            if(spt[i][j-1].nom)spt[i][j].v=spt[i][j-1].v+spt[spt[i][j-1].nom][j-1].v;
            else spt[i][j].v=spt[i][j-1].v;
        }
    }
}
int query(int nom,int v)
{
    if(!nom)return 0;
    if(v<=a[nom].v)return nom;
    int i=0;
    while(spt[nom][i].v<v && spt[nom][i].nom>0 && i<logN)i++;
    if(spt[nom][i].v>=v&&i>0)i--;
    return query(spt[nom][i].nom,v-spt[nom][i].v);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
    cin>>a[i].d>>a[i].v;
}
getLog();
make_SpTable();
int nom,v;
for(int t=0;t<q;t++)
{
    cin>>nom>>v;
    cout<<query(nom,v)<<endl;
}
return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 17996 KB Output is correct
2 Correct 205 ms 16956 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 209 ms 17996 KB Output is correct
9 Correct 205 ms 16956 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 81 ms 11716 KB Output is correct
12 Correct 296 ms 22144 KB Output is correct
13 Correct 195 ms 21520 KB Output is correct
14 Correct 141 ms 20812 KB Output is correct
15 Correct 119 ms 21088 KB Output is correct