oj.uz

Submission #978575

# Submission time Handle Problem Language Result Execution time Memory
978575 2024-05-09T11:03:57 Z parlimoos Two Antennas (JOI19_antennas) C++14
13 / 100
 690 ms 524288 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
 
const int root = 4000;
const int inroot = 200000 / root;
const int lg = int(log2(root)) + 1;
 
int n , q , o[200000];
vector<arr(3)> a;
vector<arr(2)> ops[200000];
vector<int> adds[200000] , dls[200000];
int sqrinf[inroot][2] , sqr[inroot][3];
int sqrprs[inroot][200000][lg][2][2];
bool lst[200000];
int trn , vls[200000];
 
void setMin(int &a , int b){
	a = min(a , b);
}
void setMax(int &a , int b){
	a = max(a , b);
}
void initSqr(){
	fill(&vls[0] , &vls[n] , -1);
	for(int i = 0 ; i < 200000 ; i += root){
		sqrinf[i / root][0] = i;
		sqrinf[i / root][1] = i + root - 1;
	}
	for(int i = 0 ; i < inroot ; i++){
		for(int j = 0 ; j < n ; j++){
			for(int bit = 0 ; bit < lg ; bit++){
				for(int arw = 0 ; arw < 2 ; arw++){
					sqrprs[i][j][bit][arw][0] = int(2e9);
					sqrprs[i][j][bit][arw][1] = -1;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		if(a[i][1] > i) continue;
		int l = max(0 , i - a[i][2]) , r = i - a[i][1];
		for(int sq = 0 ; sq < inroot ; sq++){
			if(sqrinf[sq][0] < l) continue;
			if(sqrinf[sq][1] > r) break;
			for(int arw = 0 ; arw < 2 ; arw++){
				setMin(sqrprs[sq][i][0][arw][0] , a[i][0]);
				setMax(sqrprs[sq][i][0][arw][1] , a[i][0]);
			}
		}
	}
	for(int sq = 0 ; sq < inroot ; sq++){
		for(int i = 0 ; i < n ; i++){
			for(int el = 1 , bit = 1 ; bit < lg and el <= i ; bit++ , el += el){
				sqrprs[sq][i][bit][0][0] = sqrprs[sq][i][bit - 1][0][0];
				setMin(sqrprs[sq][i][bit][0][0] , sqrprs[sq][i - el][bit - 1][0][0]);
				sqrprs[sq][i][bit][0][1] = sqrprs[sq][i][bit - 1][0][1];
				setMax(sqrprs[sq][i][bit][0][1] , sqrprs[sq][i - el][bit - 1][0][1]);
			}
		}
		for(int i = n - 1 ; i >= 0 ; i--){
			for(int el = 1 , bit = 1 ; bit < lg and i + el <= n - 1 ; bit++ , el += el){
				sqrprs[sq][i][bit][1][0] = sqrprs[sq][i][bit - 1][1][0];
				setMin(sqrprs[sq][i][bit][1][0] , sqrprs[sq][i + el][bit - 1][1][0]);
				sqrprs[sq][i][bit][1][1] = sqrprs[sq][i][bit - 1][1][1];
				setMax(sqrprs[sq][i][bit][1][1] , sqrprs[sq][i + el][bit - 1][1][1]);
			}
		}
	}
}
int getMin(int sq , int l , int r){
	int bit = int(log2(r - l + 1));
	return min(sqrprs[sq][r][bit][0][0] , sqrprs[sq][l][bit][1][0]);
}
int getMax(int sq , int l , int r){
	int bit = int(log2(r - l + 1));
	return max(sqrprs[sq][r][bit][0][1] , sqrprs[sq][l][bit][1][1]);
}
void delSqr(int i){
	int sq = i / root;
	lst[i] = 0 , sqr[sq][1] = int(2e9) , sqr[sq][2] = -1;
	int d1 = getMin(sq , i + a[i][1] , i + a[i][2]);
	int d2 = getMax(sq , i + a[i][1] , i + a[i][2]);
	setMax(vls[i] , max(a[i][0] - d1 , d2 - a[i][0]));
	for(int j = sqrinf[sq][0] ; j <= sqrinf[sq][1] ; j++){
		if(!lst[j]) continue;
		setMin(sqr[sq][1] , a[j][0]) , setMax(sqr[sq][2] , a[j][0]);;
	}
}
void addSqr(int i){
	int sq = i / root;
	lst[i] = 1;
	setMin(sqr[sq][1] , a[i][0]) , setMax(sqr[sq][2] , a[i][0]);
}
void updSqr(int l , int r , int val){
	for(int sq = 0 ; sq < inroot ; sq++){
		if(sqrinf[sq][0] > r) break;
		if(sqrinf[sq][1] < l) continue;
		if(sqrinf[sq][0] >= l and sqrinf[sq][1] <= r){
			int d = max(val - sqr[sq][1] , sqr[sq][2] - val);
			setMax(sqr[sq][0] , d);
		}else{
			for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
				if(!lst[i]) continue;
				setMax(vls[i] , abs(val - a[i][0]));
				setMax(sqr[sq][0] , vls[i]);
			}
		}
	}
}
int getSqr(int l , int r){
	int res = -1;
	for(int sq = 0 ; sq < inroot ; sq++){
		if(sqrinf[sq][0] > r) break;
		if(sqrinf[sq][1] < l) continue;
		if(sqrinf[sq][0] >= l and sqrinf[sq][1] <= r) setMax(res , sqr[sq][0]);
		else{
			for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
				if(!lst[i]){
					setMax(res , vls[i]);
					continue;
				}
				int d1 = getMin(sq , i + a[i][1] , min(i + a[i][2] , trn));
				int d2 = getMax(sq , i + a[i][1] , min(i + a[i][2] , trn));
				setMax(res , max({a[i][0] - d1 , d2 - a[i][0] , vls[i]}));
			}
		}
	}
	return res;
}
void f(){
	for(trn = 0 ; trn < n ; trn++){
		for(int &el : adds[trn]) addSqr(el);
		if(trn >= a[trn][1]) updSqr(max(0 , trn - a[trn][2]) , trn - a[trn][1] , a[trn][0]);
		for(auto op : ops[trn]){
			o[op[1]] = getSqr(op[0] , trn);
		}
		for(int &el : dls[trn]) delSqr(el);
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		a.pb({0 , 0 , 0});
		cin >> a.back()[0] >> a.back()[1] >> a.back()[2];
		if(i + a[i][1] < n){
			adds[i + a[i][1]].pb(i);
			if(i + a[i][2] < n - 1) dls[i + a[i][2]].pb(i);
		}
	}
	cin >> q;
	for(int i = 0 ; i < q ; i++){
		int l , r;
		cin >> l >> r;
		ops[r - 1].pb({l - 1 , i});
	}
	initSqr() , f();
	for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 90944 KB Output is correct
2 Correct 14 ms 91992 KB Output is correct
3 Correct 14 ms 93528 KB Output is correct
4 Correct 14 ms 91736 KB Output is correct
5 Correct 14 ms 93532 KB Output is correct
6 Correct 14 ms 91736 KB Output is correct
7 Correct 14 ms 93552 KB Output is correct
8 Correct 14 ms 91688 KB Output is correct
9 Correct 13 ms 90972 KB Output is correct
10 Correct 14 ms 91740 KB Output is correct
11 Correct 14 ms 90968 KB Output is correct
12 Correct 14 ms 93532 KB Output is correct
13 Correct 16 ms 93516 KB Output is correct
14 Correct 15 ms 91484 KB Output is correct
15 Correct 14 ms 93532 KB Output is correct
16 Correct 16 ms 91384 KB Output is correct
17 Correct 14 ms 95576 KB Output is correct
18 Correct 14 ms 91484 KB Output is correct
19 Correct 12 ms 75580 KB Output is correct
20 Correct 15 ms 73664 KB Output is correct
21 Correct 14 ms 75612 KB Output is correct
22 Correct 15 ms 77408 KB Output is correct
23 Correct 12 ms 77656 KB Output is correct
24 Correct 12 ms 77404 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 90944 KB Output is correct
2 Correct 14 ms 91992 KB Output is correct
3 Correct 14 ms 93528 KB Output is correct
4 Correct 14 ms 91736 KB Output is correct
5 Correct 14 ms 93532 KB Output is correct
6 Correct 14 ms 91736 KB Output is correct
7 Correct 14 ms 93552 KB Output is correct
8 Correct 14 ms 91688 KB Output is correct
9 Correct 13 ms 90972 KB Output is correct
10 Correct 14 ms 91740 KB Output is correct
11 Correct 14 ms 90968 KB Output is correct
12 Correct 14 ms 93532 KB Output is correct
13 Correct 16 ms 93516 KB Output is correct
14 Correct 15 ms 91484 KB Output is correct
15 Correct 14 ms 93532 KB Output is correct
16 Correct 16 ms 91384 KB Output is correct
17 Correct 14 ms 95576 KB Output is correct
18 Correct 14 ms 91484 KB Output is correct
19 Correct 12 ms 75580 KB Output is correct
20 Correct 15 ms 73664 KB Output is correct
21 Correct 14 ms 75612 KB Output is correct
22 Correct 15 ms 77408 KB Output is correct
23 Correct 12 ms 77656 KB Output is correct
24 Correct 12 ms 77404 KB Output is correct
25 Correct 276 ms 84560 KB Output is correct
26 Correct 97 ms 86444 KB Output is correct
27 Correct 538 ms 90708 KB Output is correct
28 Correct 668 ms 94328 KB Output is correct
29 Correct 340 ms 87120 KB Output is correct
30 Correct 503 ms 105456 KB Output is correct
31 Correct 134 ms 100944 KB Output is correct
32 Correct 656 ms 107860 KB Output is correct
33 Correct 395 ms 104496 KB Output is correct
34 Correct 348 ms 138828 KB Output is correct
35 Correct 511 ms 140020 KB Output is correct
36 Correct 679 ms 142416 KB Output is correct
37 Correct 114 ms 138832 KB Output is correct
38 Correct 611 ms 141404 KB Output is correct
39 Correct 101 ms 136496 KB Output is correct
40 Correct 399 ms 141380 KB Output is correct
41 Correct 297 ms 139744 KB Output is correct
42 Correct 690 ms 141388 KB Output is correct
43 Correct 119 ms 137640 KB Output is correct
44 Correct 329 ms 141408 KB Output is correct
45 Correct 58 ms 136712 KB Output is correct
46 Correct 374 ms 141404 KB Output is correct
47 Correct 102 ms 137112 KB Output is correct
48 Correct 431 ms 141420 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 90944 KB Output is correct
2 Correct 14 ms 91992 KB Output is correct
3 Correct 14 ms 93528 KB Output is correct
4 Correct 14 ms 91736 KB Output is correct
5 Correct 14 ms 93532 KB Output is correct
6 Correct 14 ms 91736 KB Output is correct
7 Correct 14 ms 93552 KB Output is correct
8 Correct 14 ms 91688 KB Output is correct
9 Correct 13 ms 90972 KB Output is correct
10 Correct 14 ms 91740 KB Output is correct
11 Correct 14 ms 90968 KB Output is correct
12 Correct 14 ms 93532 KB Output is correct
13 Correct 16 ms 93516 KB Output is correct
14 Correct 15 ms 91484 KB Output is correct
15 Correct 14 ms 93532 KB Output is correct
16 Correct 16 ms 91384 KB Output is correct
17 Correct 14 ms 95576 KB Output is correct
18 Correct 14 ms 91484 KB Output is correct
19 Correct 12 ms 75580 KB Output is correct
20 Correct 15 ms 73664 KB Output is correct
21 Correct 14 ms 75612 KB Output is correct
22 Correct 15 ms 77408 KB Output is correct
23 Correct 12 ms 77656 KB Output is correct
24 Correct 12 ms 77404 KB Output is correct
25 Correct 276 ms 84560 KB Output is correct
26 Correct 97 ms 86444 KB Output is correct
27 Correct 538 ms 90708 KB Output is correct
28 Correct 668 ms 94328 KB Output is correct
29 Correct 340 ms 87120 KB Output is correct
30 Correct 503 ms 105456 KB Output is correct
31 Correct 134 ms 100944 KB Output is correct
32 Correct 656 ms 107860 KB Output is correct
33 Correct 395 ms 104496 KB Output is correct
34 Correct 348 ms 138828 KB Output is correct
35 Correct 511 ms 140020 KB Output is correct
36 Correct 679 ms 142416 KB Output is correct
37 Correct 114 ms 138832 KB Output is correct
38 Correct 611 ms 141404 KB Output is correct
39 Correct 101 ms 136496 KB Output is correct
40 Correct 399 ms 141380 KB Output is correct
41 Correct 297 ms 139744 KB Output is correct
42 Correct 690 ms 141388 KB Output is correct
43 Correct 119 ms 137640 KB Output is correct
44 Correct 329 ms 141408 KB Output is correct
45 Correct 58 ms 136712 KB Output is correct
46 Correct 374 ms 141404 KB Output is correct
47 Correct 102 ms 137112 KB Output is correct
48 Correct 431 ms 141420 KB Output is correct
49 Runtime error 337 ms 524288 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -