Submission #978587

#	Time	Username	Problem	Language	Result	Execution time	Memory
978587		parlimoos	Two Antennas (JOI19_antennas)	C++14	13 / 100	822 ms	524288 KiB

antennas

//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]);
			}
		}
	}
	if(n > 2000) exit(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 / 2
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65