Submission #1276019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276019		kaiboy	Fire (JOI20_ho_t5)	C++20	7 / 100	1098 ms	31112 KiB

ho_t5

#pragma GCC optimize("O3")
#include <sys/time.h>
#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 200000;
const int  Q = 200000;
const int N_ = 2000000;

unsigned int RNG = 1;

void srand() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	RNG = tv.tv_sec ^ tv.tv_usec;
}

int rand() {
	return (RNG *= 3) >> 1;
}

int aa[N], qul[N], qur[N], tt[Q], ll_[Q], rr_[Q], hh[Q];
int zz[N_], ll[N_], rr[N_], sz[N_], bb[N_], n_, u_, l_, r_;
long long ss[N_], ans[Q];

int node(int a) {
	n_++;
	zz[n_] = rand();
	sz[n_] = 1;
	bb[n_] = ss[n_] = a;
	return n_;
}

void pul(int u) {
	int l = ll[u], r = rr[u];
	sz[u] = sz[l] + 1 + sz[r];
	ss[u] = ss[l] + bb[u] + ss[r];
}

void split(int u, int i) {
	if (!u) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (i == sz[ll[u]]) {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	} else if (i < sz[ll[u]]) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		split(rr[u], i - sz[ll[u]] - 1);
		rr[u] = l_, l_ = u;
	}
	pul(u);
}

int merge(int u, int v) {
	if (!u)
		return v;
	if (!v)
		return u;
	if (zz[u] > zz[v]) {
		rr[u] = merge(rr[u], v);
		pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		pul(v);
		return v;
	}
}

int query_a(int u, int i) {
	while (i != sz[ll[u]])
		if (i < sz[ll[u]])
			u = ll[u];
		else {
			i -= sz[ll[u]] + 1;
			u = rr[u];
		}
	return bb[u];
}

long long query_s(int u, int i) {
	long long s = 0;
	while (u && i >= 0)
		if (i < sz[ll[u]])
			u = ll[u];
		else {
			s += ss[ll[u]] + bb[u];
			i -= sz[ll[u]] + 1;
			u = rr[u];
		}
	return s;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	srand();
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int h = 0; h < q; h++)
		cin >> tt[h] >> ll_[h] >> rr_[h], ll_[h]--, rr_[h]--, hh[h] = h;
	sort(hh, hh + q, [] (int h0, int h1) { return tt[h0] < tt[h1]; });
	int cnt = 0;
	for (int l = 0, r; l + 1 < n; l = r + 1) {
		for (r = l; r + 1 < n && aa[r] > aa[r + 1]; r++)
			;
		if (l < r)
			qul[cnt] = l, qur[cnt] = r, cnt++;
	}
	for (int i = 0; i < n; i++)
		u_ = merge(u_, node(aa[i]));
	for (int g = 0, t = 1; t <= n; t++) {
		int cnt_ = 0;
		for (int z = 0; z < cnt; z++) {
			int l = qul[z], r = qur[z];
			split(u_, l);
			int a = bb[u_], u = merge(l_, u_);
			split(r_, r - sz[u]);
			int v = merge(l_, r_);
			u_ = merge(merge(u, node(a)), v);
			l++;
			if (r + 1 < n && query_a(u_, r) > query_a(u_, r + 1))
				r++;
			if (l < r)
				qul[cnt_] = l, qur[cnt_] = r, cnt_++;
		}
		cnt = cnt_;
		for (int h; g < q && tt[h = hh[g]] == t; g++) {
			int l = ll_[h], r = rr_[h];
			long long s = query_s(u_, r);
			if (l)
				s -= query_s(u_, l - 1);
			ans[h] = s;
		}
	}
	for (int h = 0; h < q; h++)
		cout << ans[h] << '\n';
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 80