Submission #1288013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288013		azamurai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3097 ms	55776 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Sz(x) (int)x.size()

const int N = 1e6 + 5;
const int block = 500;
int n, m, a[N], t[N * 4], leftt[N], rightt[N], l[N], r[N], k[N], lastl[N], lastr[N];

void build(int v = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		t[v] = a[tl];
		return;
	}
	int mid = (tl + tr) / 2;
	build(v + v, tl, mid);
	build(v + v + 1, mid + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (tl > r || l > tr) return 0;
	if (tl >= l && tr <= r) return t[v];
	int mid = (tl + tr) / 2;
	return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

bool compFS(pair<int,pair<int,int>>& p1, pair<int,pair<int,int>>& p2) {
	return (p1.fi < p2.fi) || (p1.fi == p2.fi && p1.se < p2.se);
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build();
	for (int i = 1; i <= n; i++) {
		leftt[i] = rightt[i] = -1;
		lastl[i] = lastr[i] = -1;
	}
	for (int i = 1; i <= n; i++) {
		int l = 1, r = i - 1, best = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (get(mid, i) > a[i]) l = mid + 1, best = mid;
			else r = mid - 1;
		}
		if (best != -1) leftt[i] = best, rightt[best] = i;
	}
	vector <pair<int,pair<int,int>>> seg;
	for (int i = 1; i <= m; i++) {
		cin >> l[i] >> r[i] >> k[i];
		seg.push_back(mp(l[i] / block, mp(r[i], i)));
	}
	sort(seg.begin(), seg.end(), compFS);
	int last_bl = -1, L = 1, R = 0;
	multiset <int> st;
	vector <int> ans(m + 1, 0);
	for (auto to : seg) {
		int ind = to.se.se;
		int lq = l[ind], rq = r[ind], kq = k[ind];
		if (to.fi != last_bl) {
			last_bl = to.fi;
			st.clear();
			for (int i = L; i <= R; i++) {
				lastl[i] = lastr[i] = -1;
			}
			L = R = lq;
			lastl[lq] = lq;
			lastr[lq] = lq;
		}
		while (L > lq) {
			L--;
			if (rightt[L] != -1 && lastr[rightt[L]] != -1 && lastr[rightt[L]] != rightt[L]) {
				int Right = lastr[rightt[L]];
				st.erase(st.find(a[rightt[L]] + a[Right]));
			}
			if (rightt[L] != -1 && lastr[rightt[L]] != -1) {
				int Right = lastr[rightt[L]];
				lastl[Right] = L;
				lastr[L] = Right;
				lastl[L] = L;
				st.insert(a[L] + a[Right]);
			}
			else {
				lastl[L] = lastr[L] = L;
			}
		}
		while (L < lq) {
			if (lastr[L] != L) {
				int Right = lastr[L];
				st.erase(st.find(a[Right] + a[L]));
				lastl[Right] = lastl[rightt[L]] = rightt[L];
				if (rightt[L] != Right) {
					st.insert(a[rightt[L]] + a[Right]);
				}
			}
			lastl[L] = lastr[L] = -1;
			L++;
		}
		while (R < rq) {
			R++;
			if (leftt[R] != -1 && lastl[leftt[R]] != -1 && lastl[leftt[R]] != leftt[R]) {
				int Left = lastl[leftt[R]];
				st.erase(st.find(a[leftt[R]] + a[Left]));
			}
			if (leftt[R] != -1 && lastl[leftt[R]] != -1) {
				int Left = lastl[leftt[R]];
				lastr[Left] = R;
				lastl[R] = Left;
				lastr[R] = R;
				st.insert(a[R] + a[Left]);
			}
			else {
				lastl[R] = lastr[R] = R;
			}
		}
		while (R > rq) {
			if (lastl[R] != R) {
				int Left = lastl[R];
				st.erase(st.find(a[Left] + a[R]));
				lastr[Left] = leftt[R] = leftt[R];
				if (leftt[R] != Left) {
					st.insert(a[leftt[R] + a[Left]]);
				}
			}
			lastl[R] = lastr[R] = -1;
			R--;
		}
		if (Sz(st) == 0 || *st.rbegin() <= kq) {
			ans[ind] = 1;
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	//cin >> t;
	
	for (int T = 1; T <= t; T++) {
		solve();
		cout << '\n';
	}
}

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