Submission #845901

#	Time	Username	Problem	Language	Result	Execution time	Memory
845901		HaciyevAlik	Fountain (eJOI20_fountain)	C++14	100 / 100	117 ms	24276 KiB

fountain

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//I Sawed the Demons
using ll = long long;
using ld = long double;
using ordered_set = tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>;
#define pb push_back
#define oo 1000000007
#define ff first
#define ss second
const int mx=1e5+5;
struct store {
	int d,c,next;
};
int st[22][mx],vol[22][mx];
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);    
   	int n,q; cin >> n >> q;
   	vector<store> v(n+1);
   	for(int i=1;i<=n;++i){
   		cin >> v[i].d >> v[i].c;
   	}
   	stack<pair<int,int>> s;
   	s.push({0,oo});
   	for(int i=n;i>=1;--i) {
   		while(s.top().ss<=v[i].d){
   			s.pop();
   		}
   		v[i].next=s.top().ff;
   		s.push({i,v[i].d});
   	}
   	for(int i=1;i<=n;++i) {
   		st[0][i]=v[i].next;
   		vol[0][i]=v[i].c;
   	}
   	for(int i=1;i<=20;++i) {
   		for(int j=1;j<=n;++j) {
   			st[i][j]=st[i-1][st[i-1][j]];
   			vol[i][j]=vol[i-1][j]+vol[i-1][st[i-1][j]];
   		}
   	}
   	while(q--) {
   		int r,v; cin >> r >> v;
   		for(int i=20;i>=0&&r;--i){
   			if(vol[i][r]<v) {
   				v-=vol[i][r];
   				r=st[i][r];
   			}
   		}
   		cout << r << "\n";
   	}
    return 0;
} 

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40