oj.uz

Submission #532513

# Submission time Handle Problem Language Result Execution time Memory
532513 2022-03-03T03:56:26 Z amunduzbaev Dungeon 3 (JOI21_ho_t5) C++17
100 / 100
 1312 ms 299224 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 = 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 245376 KB Output is correct
2 Correct 105 ms 245460 KB Output is correct
3 Correct 100 ms 245544 KB Output is correct
4 Correct 107 ms 245304 KB Output is correct
5 Correct 110 ms 245368 KB Output is correct
6 Correct 102 ms 245384 KB Output is correct
7 Correct 104 ms 245316 KB Output is correct
8 Correct 116 ms 245408 KB Output is correct
9 Correct 101 ms 245388 KB Output is correct
10 Correct 105 ms 245324 KB Output is correct
11 Correct 112 ms 245384 KB Output is correct
12 Correct 103 ms 245444 KB Output is correct
13 Correct 107 ms 245316 KB Output is correct
14 Correct 106 ms 245460 KB Output is correct
15 Correct 105 ms 245444 KB Output is correct
16 Correct 104 ms 245460 KB Output is correct
17 Correct 105 ms 245308 KB Output is correct
18 Correct 107 ms 245460 KB Output is correct
19 Correct 100 ms 245336 KB Output is correct
20 Correct 104 ms 245448 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 256808 KB Output is correct
2 Correct 354 ms 257076 KB Output is correct
3 Correct 281 ms 258320 KB Output is correct
4 Correct 234 ms 256736 KB Output is correct
5 Correct 358 ms 257208 KB Output is correct
6 Correct 739 ms 293872 KB Output is correct
7 Correct 1028 ms 293284 KB Output is correct
8 Correct 925 ms 299224 KB Output is correct
9 Correct 855 ms 293348 KB Output is correct
10 Correct 1168 ms 297688 KB Output is correct
11 Correct 1124 ms 296904 KB Output is correct
12 Correct 741 ms 292768 KB Output is correct
13 Correct 1018 ms 293220 KB Output is correct
14 Correct 994 ms 292940 KB Output is correct
15 Correct 784 ms 293784 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 288160 KB Output is correct
2 Correct 823 ms 292780 KB Output is correct
3 Correct 662 ms 286384 KB Output is correct
4 Correct 1010 ms 287620 KB Output is correct
5 Correct 605 ms 286840 KB Output is correct
6 Correct 824 ms 291080 KB Output is correct
7 Correct 825 ms 286292 KB Output is correct
8 Correct 582 ms 289868 KB Output is correct
9 Correct 516 ms 283956 KB Output is correct
10 Correct 805 ms 290068 KB Output is correct
11 Correct 658 ms 285556 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 245376 KB Output is correct
2 Correct 105 ms 245460 KB Output is correct
3 Correct 100 ms 245544 KB Output is correct
4 Correct 107 ms 245304 KB Output is correct
5 Correct 110 ms 245368 KB Output is correct
6 Correct 102 ms 245384 KB Output is correct
7 Correct 104 ms 245316 KB Output is correct
8 Correct 116 ms 245408 KB Output is correct
9 Correct 101 ms 245388 KB Output is correct
10 Correct 105 ms 245324 KB Output is correct
11 Correct 112 ms 245384 KB Output is correct
12 Correct 103 ms 245444 KB Output is correct
13 Correct 107 ms 245316 KB Output is correct
14 Correct 106 ms 245460 KB Output is correct
15 Correct 105 ms 245444 KB Output is correct
16 Correct 104 ms 245460 KB Output is correct
17 Correct 105 ms 245308 KB Output is correct
18 Correct 107 ms 245460 KB Output is correct
19 Correct 100 ms 245336 KB Output is correct
20 Correct 104 ms 245448 KB Output is correct
21 Correct 258 ms 256808 KB Output is correct
22 Correct 354 ms 257076 KB Output is correct
23 Correct 281 ms 258320 KB Output is correct
24 Correct 234 ms 256736 KB Output is correct
25 Correct 358 ms 257208 KB Output is correct
26 Correct 739 ms 293872 KB Output is correct
27 Correct 1028 ms 293284 KB Output is correct
28 Correct 925 ms 299224 KB Output is correct
29 Correct 855 ms 293348 KB Output is correct
30 Correct 1168 ms 297688 KB Output is correct
31 Correct 1124 ms 296904 KB Output is correct
32 Correct 741 ms 292768 KB Output is correct
33 Correct 1018 ms 293220 KB Output is correct
34 Correct 994 ms 292940 KB Output is correct
35 Correct 784 ms 293784 KB Output is correct
36 Correct 1168 ms 288160 KB Output is correct
37 Correct 823 ms 292780 KB Output is correct
38 Correct 662 ms 286384 KB Output is correct
39 Correct 1010 ms 287620 KB Output is correct
40 Correct 605 ms 286840 KB Output is correct
41 Correct 824 ms 291080 KB Output is correct
42 Correct 825 ms 286292 KB Output is correct
43 Correct 582 ms 289868 KB Output is correct
44 Correct 516 ms 283956 KB Output is correct
45 Correct 805 ms 290068 KB Output is correct
46 Correct 658 ms 285556 KB Output is correct
47 Correct 1214 ms 293096 KB Output is correct
48 Correct 961 ms 298400 KB Output is correct
49 Correct 748 ms 292004 KB Output is correct
50 Correct 1312 ms 293748 KB Output is correct
51 Correct 999 ms 292660 KB Output is correct
52 Correct 1304 ms 297240 KB Output is correct
53 Correct 989 ms 292220 KB Output is correct
54 Correct 733 ms 296356 KB Output is correct
55 Correct 680 ms 290780 KB Output is correct
56 Correct 853 ms 294816 KB Output is correct
57 Correct 820 ms 292404 KB Output is correct