oj.uz

Submission #769912

# Submission time Handle Problem Language Result Execution time Memory
769912 2023-06-30T13:05:19 Z TimDee Fountain (eJOI20_fountain) C++17
100 / 100
 279 ms 37680 KB 
//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 1e9+7;//998244353;
 
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts:  :smiling_face_with_3_hearts:  
 
//vidime sa veľmi skoro, moje slnko

const int N=1e5+5;
const int K=18;

int go[N][K];
int up[N][K];

void solve() {

	int n, q; cin>>n>>q;
	vector<pi> a(n);
	forn(i,n) cin>>a[i].f>>a[i].s;
	vector<int> to(n);
	vector<pi> st;
	st.pb({inf,-1});
	for(int i=n-1; i>=0; --i) {
		while (a[i].f >= st.back().f) st.pop_back();
		to[i]=st.back().s;
		st.pb({a[i].f,i});
	}
	forn(i,n) go[i][0]=a[i].s;// + (to[i]!=-1)?a[to[i]].s:inf;
	forn(i,n) up[i][0]=to[i];

	const int inf=2e9;
	for (int j=1; j<K; ++j) {
		forn(i,n) go[i][j]=go[i][j-1]+((up[i][j-1]!=-1)?go[up[i][j-1]][j-1]:inf);
		forn(i,n) up[i][j]=(up[i][j-1]!=-1)?up[up[i][j-1]][j-1]:up[i][j-1];
	}

	forn(i,q) {
		int r,v; cin>>r>>v; --r;
		if (a[r].s >= v) {
			cout<<r+1<<'\n'; continue;
		} 
		int z=0;
		for (int j=K-1; j>=0; --j) {
			if (r==-1) continue;
			if (go[r][j] >= v) continue;
			v-=go[r][j];
			r=up[r][j];
		}
		cout<<r+1<<'\n';
	}	

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message

fountain.cpp:3:1: warning: multi-line comment [-Wcomment]
    3 | //\
      | ^
fountain.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //   \ __ __  \
      | ^
fountain.cpp:36:1: warning: multi-line comment [-Wcomment]
   36 | // \
      | ^
fountain.cpp: In function 'void solve()':
fountain.cpp:75:7: warning: unused variable 'z' [-Wunused-variable]
   75 |   int z=0;
      |       ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 664 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 31648 KB Output is correct
2 Correct 205 ms 32492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 664 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 182 ms 31648 KB Output is correct
9 Correct 205 ms 32492 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 63 ms 19796 KB Output is correct
12 Correct 279 ms 37680 KB Output is correct
13 Correct 207 ms 36056 KB Output is correct
14 Correct 140 ms 34956 KB Output is correct
15 Correct 105 ms 35192 KB Output is correct