제출 #1287567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287567		azamurai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3095 ms	3596 KiB

sortbooks

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

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

const int N = 2e5 + 5;
const int block = 500;
int n, m, a[N], t[N], L[N], R[N], k[N], Cnt[N];

void upd(int pos, int x) {
	for (int i = pos; i < N; i += (i&(-i))) {
		t[i] += x;
	}
}

int Get(int pos) {
	int sum = 0;
	for (int i = pos; i >= 1; i -= (i&(-i))) {
		sum += t[i];
	}
	return sum;
}

int get(int l, int r) {
	return Get(r) - Get(l - 1);
}

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.fi < p2.se.fi);
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[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());
	int l = 1, r = 0, last_bl = -1, cnt = 0;
	vector <int> ans(m + 1, 0);
	for (auto to : seg) {
		int ind = to.se.se;
		int l2 = L[ind], r2 = R[ind], K = k[ind];
		if (to.fi != last_bl) {
			cnt = 0;
			for (int i = l; i <= r; i++) {
				upd(a[i], -Cnt[a[i]]);
				Cnt[a[i]] = 0;
			}
			last_bl = to.fi;
			l = l2, r = l2;
			upd(a[l], 1);
			Cnt[a[l]] = 1;
		}
		while (l > l2) {
			l--;
			if ((K - a[l] + 1) <= (a[l] - 1)) {
				cnt += get(K - a[l] + 1, a[l] - 1);
			}
			upd(a[l], 1);
			Cnt[a[l]]++;
		}
		while (l < l2) {
			if ((K - a[l] + 1) <= (a[l] - 1)) {
				cnt -= get(K - a[l] + 1, a[l] - 1);
			}
			upd(a[l], -1);
			Cnt[a[l]]--;
			l++;
		}
		while (r < r2) {
			r++;
			cnt += get(max(a[r], K - a[r]) + 1, N - 1);
			upd(a[r], 1);
			Cnt[a[r]]++;
		}
		while (r > r2) {
			cnt -= get(max(a[r], K - a[r]) + 1, N - 1);
			upd(a[r], -1);
			Cnt[a[r]]--;
			r--;
		}
		if (cnt == 0) 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