Submission #467282

#	Time	Username	Problem	Language	Result	Execution time	Memory
467282		mansur	Fountain (eJOI20_fountain)	C++17	30 / 100	276 ms	35976 KiB

fountain

#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
             		
using namespace std;
 
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long
 
const int inf = (1ll << 62ll), N = 1e5 + 2, mod = 1e9 + 7;                    
 
vector<pii> dd = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

pii up[N][18];

signed main() {
	//freopen("invtrans.in", "r", stdin);
	//freopen("invtrans.out", "w", stdout);
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int n, q;
	cin >> n >> q;
	int d[n + 1], c[n + 1], r[n + 1];
	vector<pii> s;
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> c[i];
		s.pb({d[i], i});
	}
	sort(rall(s));
	set<int> pos;
	pos.insert(n + 1);
	for (auto e: s) {
		auto it = pos.upper_bound(e.ss);
		pos.insert(e.ss);
		r[e.ss] = *it;	
	}
	for (int i = 1; i <= n; i++) {
		up[i][0] = {r[i], c[i]};	
	}

	up[n + 1][0] = {n + 1, 0};
	for (int j = 1; j < 18; j++) {
		for (int i = 1; i <= n + 1; i++) {
			up[i][j] = {up[up[i][j - 1].ff][j - 1].ff, up[i][j - 1].ss + up[up[i][j - 1].ff][j - 1].ss};
		}
	}
	while (q--) {
		int rr, v;
		cin >> rr >> v;
		for (int i = 17; i >= 0; i--) {
			if (up[rr][i].ss >= v) continue;
			v -= up[rr][i].ss;
			rr = up[rr][i].ff;
		}
		cout << (rr == n + 1 ? 0 : rr) << nl;
	}
}    	                                                        

Compilation message (stderr)

fountain.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      |

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