Submission #570472

#	Time	Username	Problem	Language	Result	Execution time	Memory
570472		8e7	Fire (JOI20_ho_t5)	C++17	100 / 100	578 ms	69596 KiB

ho_t5

//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct query{
	int l, r, id;	
	query(){l = r = id = 0;}
	query(int a, int b, int c){l = a, r = b, id = c;}
};
struct line{
	ll m, k;
	line(){m = k = 0;}
	line(ll x, ll y){m = x, k = y;}
	ll val(ll x){return m * x + k;}
	line operator +(line l){
		return line(m + l.m, k + l.k);
	}
};
struct segtree{
	line seg[4 * maxn];
	void init(int cur, int l, int r, ll a[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = line{a[l], a[l]};
			return;	
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, a), init(cur*2+1, m, r, a);
		seg[cur] = seg[cur*2] + seg[cur*2+1];
	}
	void modify(int cur, int l, int r, int ind, line li) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = li;
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind, li);
		else modify(cur*2+1, m, r, ind, li);
		seg[cur] = seg[cur*2] + seg[cur*2+1];
	}
	ll query(int cur, int l, int r, int ql, int qr, int x) {
		if (r <= l || ql >= r || qr <= l) return 0;
		if (ql <= l && qr >= r) return seg[cur].val(x);
		int m = (l + r) / 2;
		return query(cur*2, l, m, ql, qr, x) + query(cur*2+1, m, r, ql, qr, x);
	}
} tr;
struct sparse_table{
	pii sp[18][maxn];
	void build(int n, ll a[]) {
		for (int i = 1;i <= n;i++) sp[0][i] = {a[i], i};
		for (int i = 1;i < 18;i++) {
			for (int j = 1;j <= n - (1<<i) + 1;j++) {
				sp[i][j] = max(sp[i-1][j], sp[i-1][j + (1<<(i-1))]);
			}
		}
	}
	int query(int l, int r) { //[l, r]
		l = max(l, 1);
		int h = __lg(r - l + 1);
		return max(sp[h][l], sp[h][r - (1<<h) + 1]).ss;	
	}
} sp;
vector<query> que[maxn];
vector<int> ev[maxn];
ll a[maxn], ans[maxn];
int lef[maxn], rig[maxn], type[maxn];
int main() {
	io
	int n, q;
	cin >> n >> q;
	for (int i = 1;i <= n;i++) cin >> a[i];	
	for (int i = 0;i < q;i++) {
		int t, l, r;
		cin >> t >> l >> r;
		que[t].push_back(query(l, r, i));			
	}
	stack<int> stk;
	for (int i = 1;i <= n;i++) {
		while (stk.size() && a[i] >= a[stk.top()]) {
			rig[stk.top()] = i;	
			stk.pop();
		}
		if (stk.size()) lef[i] = stk.top();
		else lef[i] = -n;
		stk.push(i);
	}
	while (stk.size()) {
		rig[stk.top()] = n + 1;
		stk.pop();
	}
	for (int i = 1;i <= n;i++) {
		if (i - lef[i] - 1 < maxn) ev[i - lef[i] - 1].push_back(i);	
		if (rig[i] - i - 1 < maxn) ev[rig[i] - i - 1].push_back(i);	
		if (rig[i] - lef[i] < maxn) ev[rig[i] - lef[i]].push_back(i);
	}
	tr.init(1, 1, n+1, a);
	sp.build(n, a);
	for (int i = 0;i <= n;i++) {
		for (int j:ev[i]) {
			//debug("ch", j);
			if (type[j] < 2) {
				ll cur = tr.query(1, 1, n+1, j, j+1, i);
				tr.modify(1, 1, n+1, j, line(-type[j] * a[j], cur + type[j] * a[j] * i));
			} else {
				tr.modify(1, 1, n+1, j, line());		
			}
			type[j]++;
		}
		for (auto [l, r, id]:que[i]) {
			ans[id] = tr.query(1, 1, n+1, l - i, r+1, i);	
			debug(i, l, r);
			int mr = sp.query(r-i, r), ml = sp.query(l - i, l);
			debug(ans[id], ml, mr);
			ans[id] -= (min(rig[mr] - 1, mr + i) - r) * a[mr];
			ans[id] -= (l - max(lef[ml] + i + 1, ml)) * a[ml];
			ans[id] -= tr.query(1, 1, n+1, l - i, ml, i);
			ans[id] -= tr.query(1, 1, n+1, mr+1, r+1, i);
		}
	}
	for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
/*
10 1
3 1 4 1 5 9 2 6 5 3
3 2 8
*/

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
ho_t5.cpp:131:4: note: in expansion of macro 'debug'
  131 |    debug(i, l, r);
      |    ^~~~~
ho_t5.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
ho_t5.cpp:133:4: note: in expansion of macro 'debug'
  133 |    debug(ans[id], ml, mr);
      |    ^~~~~

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