Submission #533240

#	Time	Username	Problem	Language	Result	Execution time	Memory
533240		koioi.org-koosaga	Dungeon 3 (JOI21_ho_t5)	C++17	11 / 100	4075 ms	11688 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 = 1000050;

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

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);
	for(int i = 1; i <= n; i++) cin >> a[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});
		}
	}
	for(int i = 0; i < m; i++){
		int s, e; lint x;
		cin >> s >> e >> x;
		e--;
		bool ok = 1;
		for(int j = s; j <= e; j++){
			if(a[j] - a[j-1] > x) ok = 0;
		}
		if(!ok){
			cout << "-1\n";
			continue;
		}
		lint ret = 0;
		for(auto &j : v){
			int ns = max(s, j.s);
			int ne = min(e, j.e);
			if(ne < ns) continue;
			if(ns > s){
				ret += j.x * max(0ll, a[ne] - a[ns - 2] - x);
			}
			else{
				ret += j.x * (a[ne] - a[ns - 1]);
			}
		}
		cout << ret << "\n";
	}
}

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