Submission #1008937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008937		ByeWorld	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1554 ms	174892 KiB

sortbooks

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e6+10;
const int INF = 1e9+10;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, q;
int a[MAXN];

struct seg {
	int st[4*MAXN];
	int mrg(int x, int y){
		return max(x, y);
	}
	void bd(int id, int l, int r){
		if(l==r){ st[id] = -INF; return; }
		bd(lf, l, md); bd(rg, md+1, r);
		st[id] = -INF; 
	}
	int que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return mrg(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	int upd(int id, int l, int r, int x, int p){
		if(r<x || x<l) return st[id];
		if(l==r && l==x) return st[id] = p;
		return st[id] = mrg(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
	}
} A;

int sp[MAXN][LOG+5];
vector <ipii> que;
vector <int> vec;
int QUE(int l, int r){
	if(l > r) return -INF;
	int lg = log2(r-l+1);
	return max(sp[l][lg], sp[r-(1<<lg)+1][lg]);
}
int k[MAXN], ans[MAXN];
signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=n; i>=1; i--){
		cin >> a[i];
		sp[i][0] = a[i];
	}
	for(int j=1; j<LOG; j++) 
		for(int i=1; i<=n; i++)
			if(i+(1<<j)-1 <= n) sp[i][j] = max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
	A.bd(1, 1, n);

	for(int i=1; i<=m; i++){
		int l, r; cin >> l >> r >> k[i];
		l = n-l+1; r = n-r+1;
		que.pb({{l, r}, i});
	}
	sort(que.begin(), que.end());
	vec.pb(0); a[0] = INF; int las = 0;
	for(auto [rl, idx] : que){
		int L = rl.se, R = rl.fi;
		while(las < R){
			++las;
			while(a[vec.back()] < a[las]){
				A.upd(1, 1, n, (int)vec.size()-1, -INF); 
				vec.pop_back();
			}
			int ba = vec.back();
			vec.pb(las);
			A.upd(1, 1, n, (int)vec.size()-1, QUE(ba+1, las-1) + a[las]);
			//lasnya kasi value ini, max in
		}
		// cout << L << ' ' << R << "LR\n";
		// for(auto in : vec) cout << in << ' ';
		// cout << " stac\n";
		// for(int i=1; i<=5; i++){
		// 	cout << i << ' ' << A.que(1, 1, n, i, i) << " i\n";
		// }

		int l=1, r=(int)vec.size()-1, mid=0, cnt=0;
		while(l<=r){
			mid = md;
			if(L <= vec[mid]){
				cnt = mid; r = mid-1;
 			} else l = mid+1;
		}
		// cout << cnt << " cnt\n";
		int ret = A.que(1, 1, n, cnt+1, (int)vec.size()-1);
		// cout << ret << " ret\n";
		ret = max(ret, QUE(L, vec[cnt]-1) + a[vec[cnt]]);
		// cout << QUE(L, vec[cnt]-1) << ' '<< a[vec[cnt]] << " que\n";
		ans[idx] = ret;
		// cout << "\n\n";
	}
	for(int i=1; i<=m; i++){
		// cout << i << ' ' << ans[i] << " ans\n";
		cout << (ans[i] <= k[i]) << '\n';
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:78:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |  for(auto [rl, idx] : que){
      |           ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23