oj.uz

Submission #532512

# Submission time Handle Problem Language Result Execution time Memory
532512 2022-03-03T03:55:22 Z amunduzbaev Dungeon 3 (JOI21_ho_t5) C++17
31 / 100
 1183 ms 297940 KB 
#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 = 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 245348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 257180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 293312 KB Output is correct
2 Correct 849 ms 297940 KB Output is correct
3 Correct 675 ms 291632 KB Output is correct
4 Correct 1078 ms 293028 KB Output is correct
5 Correct 644 ms 292228 KB Output is correct
6 Correct 815 ms 296228 KB Output is correct
7 Correct 839 ms 291496 KB Output is correct
8 Correct 589 ms 295228 KB Output is correct
9 Correct 531 ms 289232 KB Output is correct
10 Correct 835 ms 294968 KB Output is correct
11 Correct 654 ms 291504 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 245348 KB Output isn't correct
2 Halted 0 ms 0 KB -