Submission #532513

#	Time	Username	Problem	Language	Result	Execution time	Memory
532513		amunduzbaev	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	1312 ms	299224 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define ar array

const int N = 2e5 + 5;
const int M = 1e9 + 5;

struct node{
	int lx, rx, add;
	node (){
		lx = rx = add = 0;
	}
};

struct STmx{
	ar<int, 2> tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = {v, i}; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {-M, -M};
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}T, tt;

struct ST{
	node tree[N * 25];
	int last;
	
	ST(){
		last = 0;
	}
	
	void make(int x){
		if(!tree[x].lx) tree[x].lx = ++last;
		if(!tree[x].rx) tree[x].rx = ++last;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = M, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x].add += v;
			return;
		} int m = (lx + rx) >> 1;
		make(x);
		add(l, r, v, lx, m, tree[x].lx), add(l, r, v, m+1, rx, tree[x].rx);
	}
	
	int get(int i, int lx = 0, int rx = M, int x = 0){
		if(lx == rx) return tree[x].add;
		int m = (lx + rx) >> 1;
		if(i <= m && tree[x].lx) return get(i, lx, m, tree[x].lx) + tree[x].add;
		if(m < i && tree[x].rx) return get(i, m+1, rx, tree[x].rx) + tree[x].add;
		return tree[x].add;
	}
}tree, cnt;

int a[N], b[N], x[N];
vector<int> q[N], par[N];
int res[N], s[N], t[N], u[N];
int lx[N], rx[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) x[i] = x[i-1] + a[i-1];
	b[n] = M;
	for(int i=0;i<=n;i++) T.sett(i, a[i]), tt.sett(i, -b[i]);
	
	for(int i=0;i<m;i++){
		cin>>s[i]>>t[i]>>u[i];
		t[i]--, s[i]--;
		
		if(T.get(s[i], t[i] - 1)[0] <= u[i]){
			int j = lower_bound(x, x+n+1, x[t[i]] - u[i]) - x;
			j = max(s[i], j);
			j = tt.get(j, t[i])[1];
			
			q[s[i]].push_back(i);
			q[j].push_back(-i - 1);
			res[i] += (x[t[i]] - x[j]) * b[j];
		} else {
			res[i] = -1;
		}
	}
	
	vector<int> ss;
	for(int i=n-1;~i;i--){
		while(!ss.empty() && b[ss.back()] >= b[i]) ss.pop_back();
		if(ss.empty()) rx[i] = n;
		else rx[i] = ss.back();
		ss.push_back(i);
	}
	
	ss.clear();
	for(int i=0;i<n;i++){
		while(!ss.empty() && b[ss.back()] > b[i]) ss.pop_back();
		if(ss.empty()) lx[i] = -1;
		else lx[i] = ss.back();
		ss.push_back(i);
	}
	
	for(int i=0;i<n;i++){
		if(~lx[i]) par[lx[i]].push_back(i);
	}
	
	//~ for(int i=0;i<n;i++) cout<<rx[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=0;i<n;i++) cout<<lx[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=n-1;~i;i--){
		tree.add(0, x[rx[i]] - x[i] - 1, x[i] * b[i]);
		cnt.add(0, x[rx[i]] - x[i] - 1, 1 * b[i]);
		tree.add(x[rx[i]] - x[i], M, x[rx[i]] * b[i]);
		tree.add(0, M, -x[i] * b[i]);
		
		for(auto j : par[i]){
			int l = lx[j], r = rx[j];
			int MX = x[r] - x[l];
			tree.add(0, M, x[j] * b[j]);
			tree.add(MX + 1, M, -x[r] * b[j]);
			
			tree.add(x[j] - x[l] + 1, MX, -x[l] * b[j]);
			cnt.add(x[j] - x[l] + 1, MX, -1 * b[j]);
			tree.add(0, x[j] - x[l], -x[j] * b[j]);
		}
		
		for(auto j : q[i]){
			if(j >= 0){
				res[j] += (tree.get(u[j]) + cnt.get(u[j]) * u[j]);
			} else {
				j = abs(j) - 1;
				res[j] -= (tree.get(u[j]) + cnt.get(u[j]) * u[j]);
			}
		}
	}
	
	for(int i=0;i<m;i++) cout<<res[i]<<"\n";
}

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