Submission #342192

#	Time	Username	Problem	Language	Result	Execution time	Memory
342192		antin_kuntin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1657 ms	71520 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define int long long int
#define endl '\n'
#define MOD (int)(1e9 + 7)
#define all(x) x.begin(), x.end()
#define mid start+(end-start)/2
#define debug(x) cerr << #x << " = " << x << endl
#define binary(x) cerr << #x << " = " << bitset<8>(x) << endl
#define N (int)(1e6)+5

int n, m, a, b, c;
vector<int> v;
vector<pair<pair<int, int>, pair<int, int> > > q;
int tree[4*N];
int cevs[N];

void update(int wai, int start, int end, int indis, int val){
	if(start > indis || end < indis) return;
	if(start == end){
		tree[wai] = max(tree[wai], val);
		return;
	}
	update(wai*2, start, mid, indis, val), update(wai*2+1, mid+1, end, indis, val);
	tree[wai] = max(tree[wai*2], tree[wai*2+1]);
}

int query(int wai, int start, int end, int l, int r){
	if(start > r || end < l) return 0;
	if(start >= l && end <= r) return tree[wai];
	return max(query(wai*2, start, mid, l, r), query(wai*2+1, mid+1, end, l, r));
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a;
		v.pb(a);
	}
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		q.pb({{a,b}, {c, i}});
	}
	sort(all(q));
	stack<pair<int, int> > st;
	int las = m-1;
	for(int i = n-1; i >= 0; i--){
		int son = i;
		while(!st.empty() && v[i] > st.top().st){
			update(1, 1, n, son+2, v[i]+st.top().st);
			son = st.top().nd;
			st.pop();
		}
		if(st.empty()) son = n-1;
		st.push({v[i], son});
		while(las >= 0 && q[las].st.st == i+1){
			// debug(query(1, 1, n, i, q[las].st.nd));
			if(query(1, 1, n, i+1, q[las].st.nd) <= q[las].nd.st) cevs[q[las].nd.nd] = 1;
			las--;
		}
	}
	for(int i = 0; i < m; i++) cout << cevs[i] << endl;
}

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