Submission #334033

#	Time	Username	Problem	Language	Result	Execution time	Memory
334033		ChrisT	Fire (JOI20_ho_t5)	C++17	100 / 100	607 ms	64608 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
const int MN = 4e5 + 5;
struct Query {
	int id,l,r;
};
long long ans[MN];
struct withT {
	long long bit[MN], bit2[MN];
	void update (int a, int mult) {
		for (int i = max(1,mult); i < MN; i += i & -i) {
			bit[i] += mult * 1LL * a;
			bit2[i] += a;
		}
	}
	array<long long,2> query (int l, int r) {
		long long ret = 0, ret2 = 0;
		for (int i = r; i>0; i ^= i & -i) {
			ret += bit[i];
			ret2 += bit2[i];
		}
		for (int i = l-1; i>0; i ^= i & -i) {
			ret -= bit[i];
			ret2 -= bit2[i];
		}
		return {ret,ret2};
	}
} rT, lT;
struct noT {
	long long bit[MN];
	void update (int i, long long v) {
		for (;i<MN;i+=i&-i)
			bit[i] += v;
	}
	long long query (int l, int r) {
		long long ret = 0;
		for (;r;r^=r&-r)
			ret += bit[r];
		for (--l;l>0;l^=l&-l)
			ret -= bit[l];
		return ret;
	}
} rNoT, lNoT;
int main() {
	int n,q;
	scanf ("%d %d",&n,&q);
	vector<int> a(n+1), nxt(n+1), lst(n+1), stk;
	vector<vector<int>> die(n+2), ch1(n+2), ch2(n+2);
	for (int i = 1; i <= n; i++) {
		scanf ("%d",&a[i]);
		while (!stk.empty() && a[stk.back()] < a[i])
			stk.pop_back();
		lst[i] = stk.empty() ? -1e9 : stk.back();
		stk.push_back(i);
	}
	stk.clear();
	for (int i = n; i >= 1; i--) {
		while (!stk.empty() && a[stk.back()] <= a[i])
			stk.pop_back();
		nxt[i] = stk.empty() ? 1e9 : stk.back();
		int ded = min(n+1,min(nxt[i],n+1) - lst[i] - 1);
		die[ded].push_back(i);
		ch1[min(ded,nxt[i] - i - 1)].push_back(i);
		ch2[min(ded,i - lst[i] - 1)].push_back(i);
		stk.push_back(i);
	}
	vector<vector<Query>> queries(n+1);
	for (int i = 0; i < q; i++) {
		int t,l,r;
		scanf ("%d %d %d",&t,&l,&r);
		queries[t].push_back({i,l,r});
	}
	multiset<pair<int,int>> slT,slNoT,srT,srNoT;
	for (int t = n; t >= 1; t--) {
		for (int i : die[t+1]) { //revival
			srNoT.insert({nxt[i],a[i]});
			rNoT.update(nxt[i],a[i] * 1LL * nxt[i]);
			slT.insert({lst[i] + 1,a[i]});
			lT.update(a[i],lst[i] + 1);
		}
		for (int i : ch1[t+1]) { //rNoT --> rT
			rNoT.update(nxt[i],-a[i] * 1LL * nxt[i]);
			srNoT.erase(srNoT.find({nxt[i],a[i]}));
			rT.update(a[i],i+1);
			srT.insert({i+1,a[i]});
		}
		for (int i : ch2[t+1]) { //lT --> lNoT
			lT.update(-a[i],lst[i] + 1);
			slT.erase(slT.find({lst[i] + 1,a[i]}));
			lNoT.update(i,a[i] * 1LL * i);
			slNoT.insert({i,a[i]});
		}
		for (auto &[idx,l,r] : queries[t]) {
			auto [r1,r2] = rT.query(l-t+1,r-t);
			auto [l1,l2] = lT.query(l-t,r-t);
			long long sum = rNoT.query(l+1,r) + r1 + r2 * t - lNoT.query(l,r) - l1 - l2 * t;
			{
				pair<int,int> mxL = {0,0};
				auto it = slNoT.upper_bound(pair(l,(int)1e9));
				if (it != slNoT.begin()) mxL = *prev(it);
				it = slT.upper_bound(pair(l-t,(int)1e9));
				if (it != slT.begin()) mxL = max(mxL,pair(prev(it)->first+t,prev(it)->second));
				if (mxL.first != l) sum -= (long long)mxL.second * l;
			}
			{
				pair<int,int> nxtR = {n+5,n+5};
				auto it = srNoT.upper_bound(pair(r,(int)1e9));
				if (it != srNoT.end()) nxtR = *it;
				it = srT.upper_bound(pair(r-t,(int)1e9));
				if (it != srT.end()) {
					nxtR = min(nxtR,pair(min(it->first+t,n+1),it->second));
				}
				sum += (long long)nxtR.second * (r+1);
			}
			ans[idx] = sum;
		}
	}
	for (int i = 0; i < q; i++) printf ("%lld\n",ans[i]);
    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf ("%d %d",&n,&q);
      |  ~~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf ("%d",&a[i]);
      |   ~~~~~~^~~~~~~~~~~~
ho_t5.cpp:70:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf ("%d %d %d",&t,&l,&r);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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