oj.uz

Submission #614124

# Submission time Handle Problem Language Result Execution time Memory
614124 2022-07-30T19:20:31 Z amunduzbaev Two Antennas (JOI19_antennas) C++17
22 / 100
 426 ms 47848 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll
#define sow cerr<<"here"<<endl;

const int N = 2e5 + 5;
const int inf = 2e9;
struct ST{
	int tree[N << 2], mx[N << 2];
	int cost[N << 2];
	
	void init(){
		memset(tree, 0, sizeof tree);
		memset(cost, -1, sizeof cost);
		memset(mx, 0, sizeof mx);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		mx[x << 1] = max(mx[x << 1], mx[x]);
		mx[x << 1 | 1] = max(mx[x << 1 | 1], mx[x]);
		cost[x << 1] = max(cost[x << 1], mx[x << 1] - tree[x << 1]);
		cost[x << 1 | 1] = max(cost[x << 1 | 1], mx[x << 1 | 1] - tree[x << 1 | 1]);
		mx[x] = 0;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x] = v, mx[x] = 0;
			//~ cost[x] = -1;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
		
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mx[x] = max(mx[x], v);
			cost[x] = max(cost[x], mx[x] - tree[x]);
			//~ cout<<lx<<" "<<rx<<" "<<v<<" "<<cost[x]<<" <-\n";
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -inf;
		if(lx >= l && rx <= r){
			//~ cout<<lx<<" "<<rx<<" "<<cost[x]<<endl;
			return cost[x];
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get2(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -inf;
		if(lx >= l && rx <= r){
			return mx[x];
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get2(l, r, lx, m, x << 1), get2(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int pos(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) return pos(i, lx, m, x << 1);
		else return pos(i, m + 1, rx, x << 1 | 1);
	}
}tree; 

int h[N], a[N], b[N];
int l[N], r[N], res[N];
vector<ar<int, 2>> Q[N];
int n, q;
int mx[N], mn[N];
int cost[N];

/*

5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

*/

void solve(){
	tree.init();
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return r[i] < r[j];
	});
	
	memset(cost, -1, sizeof cost);
	//~ auto set = [&](int i, int v){
		//~ mn[i] = v, mx[i] = 0;
	//~ };
	for(int i=0;i<n;i++){
		tree.set(i, inf);
		//~ set(i, inf);
	}
	//~ auto add = [&](int l, int r, int v){
		//~ for(int i=l;i<=r;i++){
			//~ mx[i] = max(mx[i], v);
			//~ cost[i] = max(cost[i], mx[i] - mn[i]);
		//~ }
	//~ };
	//~ auto get = [&](int l, int r){
		//~ int res = 0;
		//~ for(int i=l;i<=r;i++){
			//~ res = max(res, cost[i]);
		//~ }
		//~ return res;
	//~ };
	
	int j = 0;
	for(int i=0;i<n;i++){
		for(auto [j, t] : Q[i]){
			if(t){
				//~ set(j, h[j]);
				tree.set(j, h[j]);
			} else {
				//~ set(j, inf);
				tree.set(j, inf);
			}
		} Q[i].clear();
		
		int L = max(i - b[i], 0ll), R = i - a[i];
		if(L <= R){
			//~ cout<<L<<" "<<R<<" "<<h[i]<<"\n";
			tree.add(L, R, h[i]);
			//~ add(L, R, h[i]);
		}
		//~ cout<<"s\n";
		//~ for(int j=0;j<n;j++) tree.get(j, j);
		//~ cout<<"e"<<endl;
		
		Q[min(i + a[i], n)].push_back({i, 1});
		Q[min(i + b[i] + 1, n)].push_back({i, 0});
		
		while(j < q && r[p[j]] == i){
			res[p[j]] = max(res[p[j]], tree.get(l[p[j]], r[p[j]]));
			j++;
		}
	} Q[n].clear();
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	//~ freopen("in.txt", "r", stdin);
	//~ freopen("out.txt", "r", stdin);
	cin >> n;
	for(int i=0;i<n;i++) cin >> h[i] >> a[i] >> b[i];
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i];
		l[i]--, r[i]--;
	}
	memset(res, -1, sizeof res);
	solve();
	reverse(h, h + n);
	reverse(a, a + n);
	reverse(b, b + n);
	for(int i=0;i<q;i++) l[i] = n - l[i] - 1, r[i] = n - r[i] - 1, swap(l[i], r[i]);
	solve();
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 40680 KB Output is correct
2 Correct 401 ms 46228 KB Output is correct
3 Correct 263 ms 40520 KB Output is correct
4 Correct 392 ms 46208 KB Output is correct
5 Correct 156 ms 35676 KB Output is correct
6 Correct 392 ms 46120 KB Output is correct
7 Correct 331 ms 43704 KB Output is correct
8 Correct 391 ms 46240 KB Output is correct
9 Correct 56 ms 30020 KB Output is correct
10 Correct 426 ms 46220 KB Output is correct
11 Correct 217 ms 39224 KB Output is correct
12 Correct 389 ms 46140 KB Output is correct
13 Correct 288 ms 47504 KB Output is correct
14 Correct 262 ms 47352 KB Output is correct
15 Correct 263 ms 46776 KB Output is correct
16 Correct 250 ms 46540 KB Output is correct
17 Correct 294 ms 47848 KB Output is correct
18 Correct 261 ms 46724 KB Output is correct
19 Correct 276 ms 47164 KB Output is correct
20 Correct 259 ms 47224 KB Output is correct
21 Correct 252 ms 47672 KB Output is correct
22 Correct 271 ms 47424 KB Output is correct
23 Correct 273 ms 47440 KB Output is correct
24 Correct 252 ms 45940 KB Output is correct

Subtask #4
0 / 65.0

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