oj.uz

Submission #853457

# Submission time Handle Problem Language Result Execution time Memory
853457 2023-09-24T11:26:25 Z heartbeat Fountain (eJOI20_fountain) C++14
100 / 100
 173 ms 24272 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16860 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16860 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 2 ms 16884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 19796 KB Output is correct
2 Correct 104 ms 22708 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16860 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16860 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 2 ms 16884 KB Output is correct
8 Correct 87 ms 19796 KB Output is correct
9 Correct 104 ms 22708 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 49 ms 20060 KB Output is correct
12 Correct 173 ms 24272 KB Output is correct
13 Correct 101 ms 23344 KB Output is correct
14 Correct 76 ms 22472 KB Output is correct
15 Correct 59 ms 22868 KB Output is correct