Submission #533250

#	Time	Username	Problem	Language	Result	Execution time	Memory
533250		koioi.org-koosaga	Dungeon 3 (JOI21_ho_t5)	C++17	11 / 100	4098 ms	25108 KiB

Main

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 200050;
const int MAXT = 530000;

struct intv{
	int s, e; lint x;
};

struct query{
	int s, e; lint x; int idx;
};

struct bit{
	lint tree[MAXN];
	void add(int x, lint v){
		for(int i = x; i < MAXN; i += i & -i) tree[i] += v;
	}
	lint query(int x){
		lint ret = 0;
		for(int i = x; i; i -= i & -i) ret += tree[i];
		return ret;
	}
	lint query(int s, int e){ return query(e) - query(s - 1); }
}bit1, bit2;

struct seg{
	int tree[MAXT], lim;
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
	}
	void upd(int x, int v){
		for(int i = x+lim; i; i >>= 1){
			tree[i] = max(tree[i], v);
		}
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		int ret = 0;
		while(s < e){
			if(s%2 == 1) ret = max(ret, tree[s++]);
			if(e%2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<lint> a(n + 1), b(n);
	seg.init(n);
	for(int i = 1; i <= n; i++){
		cin >> a[i], a[i] += a[i - 1];
		seg.upd(i, a[i] - a[i-1]);
	}
	for(int i = 0; i < n; i++) cin >> b[i];
	vector<intv> v;
	{
		vector<int> stk;
		vector<int> l(n), r(n);
		for(int i = 0; i < n; i++){
			while(sz(stk) && b[stk.back()] > b[i]){
				stk.pop_back();
			}
			l[i] = (sz(stk) ? stk.back() : -1);
			stk.push_back(i);
		}
		stk.clear();
		for(int i = n-1; i >= 0; i--){
			while(sz(stk) && b[stk.back()] >= b[i]){
				stk.pop_back();
			}
			r[i] = (sz(stk) ? stk.back() : n);
			stk.push_back(i);
		}
		stk.clear();
		for(int i = 0; i < n; i++){
			lint lo = 0;
			if(l[i] >= 0) lo = max(lo, b[l[i]]);
			if(r[i] < n) lo = max(lo, b[r[i]]);
			v.push_back({l[i] + 2, r[i], b[i] - lo});
		}
	}
	vector<lint> ans(m);
	vector<query> qry;
	for(int i = 0; i < m; i++){
		int s, e; lint x;
		cin >> s >> e >> x;
		e--;
		if(seg.query(s, e) > x){
			ans[i] = -1;
			continue;
		}
		qry.push_back({s, e, x, i});
	}
	sort(all(v), [&](const intv &a, const intv &b){
		return a.s < b.s;
	});
	sort(all(qry), [&](const query &a, const query &b){
		return a.s < b.s;
	});
	int pv = 0, pq = 0;
	for(int i = 1; i <= n; i++){
		while(pv < sz(v) && v[pv].s == i){
			bit1.add(v[pv].e, v[pv].x);
			bit2.add(v[pv].e, v[pv].x * a[v[pv].e]);
			pv++;
		}
		while(pq < sz(qry) && qry[pq].s == i){
			auto Q = qry[pq++];
			ans[Q.idx] += (a[Q.e] - a[Q.s - 1]) * bit1.query(Q.e, n);
			ans[Q.idx] += bit2.query(Q.s, Q.e - 1);
			ans[Q.idx] -= a[Q.s - 1] * bit1.query(Q.s, Q.e - 1);
		}
	}
	for(auto &x : qry){
		for(auto &j : v){
			if(j.s > x.s){
				if(j.e > x.e) ans[x.idx] += j.x * max(0ll, a[x.e] - a[j.s - 2] - x.x);
				else ans[x.idx] += j.x * max(0ll, a[j.e] - a[j.s - 2] - x.x);
			}
		}
	}
	for(auto &a : ans) cout << a << "\n";
}

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