제출 #541988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541988		8e7	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	930 ms	210360 KiB

Main

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
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 pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct sparse_segtree{
	struct node{
		ll m, tag, k;
		node *lef, *rig;
		node(){m = tag = k = 0, lef = rig = NULL;}
		node(ll a, ll b, ll c){m = a, tag = b, k = c;}
	};
	node *root = new node();	
	void add(node * &x) {
		if (x == NULL) {
			x = new node();
		}
	}
	ll calc(int l, int r, ll m) {
		return m * (l + r - 1) * (r - l) / 2;
	}
	void modify(node *cur, ll l, ll r, ll ql, ll qr, ll m, ll k) {
		//if (cur == root) debug(ql, qr, m, k);
		if (r <= l || qr <= l || ql >= r) return;
		if (ql <= l && qr >= r) {
			cur->m += m;
			cur->tag += k;	
			return;
		}
		ll mid = (l + r) / 2;	
		add(cur->lef), add(cur->rig); 
		modify(cur->lef, l, mid, ql, qr, m, k);	
		modify(cur->rig, mid, r, ql, qr, m, k);
		cur->k = cur->lef->k + cur->rig->k + calc(l, m, cur->lef->m) + calc(m, r, cur->rig->m) + 
			cur->lef->tag + cur->rig->tag;
	}	
	ll query(node *cur, ll l, ll r, int x) {
		if (r <= l || x < l || x >= r) return 0;
		if (r - l == 1) return calc(l, r, cur->m) + cur->k + cur->tag;
		ll m = (l + r) / 2;
		ll lef = (cur->lef ? query(cur->lef, l, m, x) : 0);
		ll rig = (cur->rig ? query(cur->rig, m, r, x) : 0);
		return (x < m ? lef : rig) + cur->tag + cur->m * x;
	}
} tr;

struct segtree{
	pii seg[4*maxn];
	int type = 0;
	void init(int cur, int l, int r, ll a[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = {a[l], l};
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, a), init(cur*2+1, m, r, a);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
		if (type == 1) seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return (type ? make_pair(0LL, (ll)l) : make_pair(inf, (ll)l));
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		pii vl = query(cur*2, l, m, ql, qr), vr = query(cur*2+1, m, r, ql, qr);
		if (type) return max(vl, vr);
		else return min(vl,vr);
	}
} ma, mb;
struct query{
	int c, u, id;	
	query(){c = u = id = 0;}
	query(int b, int p, int q){c = b, u = p, id = q;}
};
ll a[maxn], b[maxn], pref[maxn];
int prv[maxn];
vector<query> que[maxn];
ll ans[maxn];
int main() {
	io
	int n, m;
	cin >> n >> m;	
	for (int i = 1;i<= n;i++) cin >> a[i], pref[i] = a[i] + pref[i-1];
	for (int i = 1;i <= n;i++) cin >> b[i];
	ma.type = 1;
	ma.init(1, 1, n+1, a);
	mb.init(1, 1, n+1, b);
	stack<int> stk;		
	for (int i = 0;i < m;i++) {
		int s, t, u;
		cin >> s >> t >> u;
		if (ma.query(1, 1, n+1, s, t).ff > u) {
			ans[i] = -1;
		} else {
			que[s].push_back(query(1, u, i));
			ll X = max(pref[s-1], pref[t-1] - u);
			int ind = lower_bound(pref, pref + n + 1, X) - pref;
			pii best = mb.query(1, 1, n+1, ind + 1, t);
			//debug(i, X, ind, best.ff, best.ss);
			ans[i] += (pref[t-1] - pref[best.ss-1]) * best.ff;
			que[best.ss].push_back(query(-1, u, i));
		}
	}	
	const int mu = 100000005;
	
	for (int i = n;i >= 1;i--) {
		while (stk.size() && b[i] < b[stk.top()]) {
			int cur = stk.top();
			stk.pop();
			ll pnt = pref[cur-1] - pref[i-1] + 1;
			if (pnt < mu) {
				tr.modify(tr.root, 0, mu, pnt, mu, -b[cur], -b[cur] * (1 - pnt));
				ll len = pref[prv[cur]-1] - pref[i-1] + 1;
				tr.modify(tr.root, 0, mu, len, mu, b[cur], b[cur] * (1 - len));
			}
		}	
		prv[i] = (stk.size() ? stk.top() : n+1);
		stk.push(i);
		tr.modify(tr.root, 0, mu, 0, mu, b[i], 0); //ok
		ll len = pref[prv[i]-1] - pref[i-1] + 1;
		tr.modify(tr.root, 0, mu, len, mu, -b[i], -b[i] * (1 - len)); //ok

		for (auto q:que[i]) {
			ans[q.id] += q.c * tr.query(tr.root, 0, mu, q.u);	
		}
		/*
		for (int j = 1;j <= 10;j++) {
			cout << tr.query(tr.root, 0, mu, j) << " ";
		}
		cout << "\n";
		*/
	}	
	for (int i = 0;i < m;i++) cout << ans[i] << "\n";
}
/*
5 4
3 4 1 2 2
2 5 1 2 1
3 6 1
3 6 2
3 6 3

3 4
1 2 2
1 2 1
1 4 1
1 4 2
1 4 3
1 4 4

5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9
*/

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44