oj.uz

Submission #532475

# Submission time Handle Problem Language Result Execution time Memory
532475 2022-03-03T02:16:21 Z amunduzbaev Dungeon 3 (JOI21_ho_t5) C++17
31 / 100
 1052 ms 283888 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{
	int tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; 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]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1e9;
		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;

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];
	for(int i=0;i<=n;i++) T.sett(i, a[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]) <= u[i]){
			q[s[i]].push_back(i);
		} 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--){
		//~ for(int j=0;j<15;j++) cout<<tree.get(j)<<" ";
		//~ cout<<"\n";
		//~ for(int j=0;j<15;j++) cout<<cnt.get(j)<<" ";
		//~ cout<<"\n\n";
		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]){
			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 114 ms 245080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 253352 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 1052 ms 279512 KB Output is correct
2 Correct 723 ms 283888 KB Output is correct
3 Correct 561 ms 277844 KB Output is correct
4 Correct 898 ms 279600 KB Output is correct
5 Correct 538 ms 278980 KB Output is correct
6 Correct 706 ms 283052 KB Output is correct
7 Correct 767 ms 278212 KB Output is correct
8 Correct 506 ms 281764 KB Output is correct
9 Correct 446 ms 276148 KB Output is correct
10 Correct 723 ms 280772 KB Output is correct
11 Correct 575 ms 278104 KB Output is correct

Subtask #4
0 / 44.0

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