제출 #979147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979147		parlimoos	Two Antennas (JOI19_antennas)	C++14	100 / 100	1631 ms	43684 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 = 400;
const int inroot = 200000 / 400;

int n , q , o[200000] , vls[200000];
vector<arr(3)> a;
vector<arr(2)> qs , ops[200000];
int sqrinf[inroot][2] , sqr[inroot][2];
bool lst[200000] , tail[inroot];
vector<int> sqrvc[inroot] , adds[200000] , dls[200000];
multiset<arr(2)> sqrset[inroot];

void initQs(){
	for(int i = 0 ; i < n ; i++) ops[i].cl();
	for(int i = 0 ; i < q ; i++){
		ops[qs[i][1]].pb({qs[i][0] , i});
	}
}
void initAnts(){
	for(int i = 0 ; i < n ; i++) adds[i].cl() , dls[i].cl();
	for(int i = 0 ; i < n ; i++){
		if(i + a[i][1] >= n) continue;
		adds[i + a[i][1]].pb(i) , dls[min(n - 1 , i + a[i][2])].pb(i);
	}
}
void initSqr(){
	fill(&lst[0] , &lst[n] , 0) , fill(&tail[0] , &tail[inroot] , 0) , 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++){
		sqrset[i].cl() , sqrvc[i].cl();
		sqr[i][0] = -1 , sqr[i][1] = -1;
	}
}
void addVc(int sq , int el){
	bool flg = 0;
	while(!sqrvc[sq].empty() and a[sqrvc[sq].back()][0] >= a[el][0]){
		flg = 1 , sqrvc[sq].pp();
	}
	if(flg or tail[sq]) sqrvc[sq].pb(el);
	tail[sq] = 0;
}
void addSqr(int el){
//	cout << el << "#\n";
	int sq = el / root;
	tail[sq] = 1 , lst[el] = 1 , sqr[sq][1] = max(sqr[sq][1] , a[el][0]);
	sqrset[sq].insert({el + a[el][1] , el});
}
void delSqr(int el){
	int sq = el / root , l = el + a[el][1];
	lst[el] = 0 , sqr[sq][1] = -1 , sqrset[sq].erase({el + a[el][1] , el});
	auto itr = lb(sqrvc[sq].bg() , sqrvc[sq].end() , l);
	if(!sqrvc[sq].empty() and itr != sqrvc[sq].end()) vls[el] = max(vls[el] , a[el][0] - a[*itr][0]);
	
	for(int i = sqrinf[sq][0] ; i <= sqrinf[sq][1] ; i++){
		if(!lst[i]) continue;
		sqr[sq][1] = max(sqr[sq][1] , a[i][0]);
	}
}
int getPrt(int l , int r){
	int sq = l / root , res = -1;
	int inx = int(sqrvc[sq].size());
	for(int i = l ; i <= r ; i++) res = max(res , vls[i]);
	if(sqrset[sq].empty() or sqrvc[sq].empty()) return res;
	auto itr = --sqrset[sq].end();
	while(true){
		while(inx > 0 and sqrvc[sq][inx - 1] >= (*itr)[0]) inx--;
		if(l <= (*itr)[1] and (*itr)[1] <= r and inx < int(sqrvc[sq].size())){
			res = max(res , a[(*itr)[1]][0] - a[sqrvc[sq][inx]][0]);
		}
		if(itr == sqrset[sq].bg()) break;
		itr--;
	}
	return res;
}
void updSqr(int l , int r , int el){
//	cout << l << " " << r << " : " << el << "$$\n";
	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){
			addVc(sq , el) , sqr[sq][0] = max(sqr[sq][0] , sqr[sq][1] - a[el][0]);
		}else{
			for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
//				cout << i << "##\n";
				if(!lst[i]) continue;
				vls[i] = max(vls[i] , a[i][0] - a[el][0]);
//				cout << i << " " << a[el][0] << "!!\n";
				sqr[sq][0] = max(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){
			res = max(res , sqr[sq][0]);
		}else{
			res = max(res , getPrt(max(l , sqrinf[sq][0]) , min(r , sqrinf[sq][1])));
		}
	}
//	cout << res << ":\n";
	return res;
}
void f(){
	for(int r = 0 ; r < n ; r++){
		for(int el : adds[r]) addSqr(el);
		if(r >= a[r][1]) updSqr(max(0 , r - a[r][2]) , r - a[r][1] , r);
		for(auto op : ops[r]) o[op[1]] = max(o[op[1]] , getSqr(op[0] , r));
		for(int el : dls[r]) delSqr(el);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("in.txt" , "r" , stdin);
	
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		a.pb({0 , 0 , 0});
		cin >> a.back()[0] >> a.back()[1] >> a.back()[2];
	}
	cin >> q;
	for(int i = 0 ; i < q ; i++){
		int l , r;
		cin >> l >> r;
		qs.pb({l - 1 , r - 1});
	}
	fill(&o[0] , &o[q] , -1);
	initSqr() , initQs() , initAnts() , f();
	
	reverse(a.bg() , a.end());
	for(int i = 0 ; i < q ; i++){
		int d1 = n - 1 - qs[i][0] , d2 = n - 1 - qs[i][1];
		qs[i][0] = d2 , qs[i][1] = d1;
	}
	initSqr() , initQs() , initAnts() , f();
	
	for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65