oj.uz

답안 #979106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979106 2024-05-10T08:57:09 Z parlimoos Two Antennas (JOI19_antennas) C++14
24 / 100
 731 ms 29020 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 = 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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14940 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 5 ms 14936 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 5 ms 15452 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 6 ms 14940 KB Output is correct
10 Correct 6 ms 14940 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 5 ms 14940 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 5 ms 14940 KB Output is correct
15 Correct 5 ms 15036 KB Output is correct
16 Correct 5 ms 14940 KB Output is correct
17 Correct 5 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 5 ms 15000 KB Output is correct
21 Correct 5 ms 14784 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 5 ms 14940 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14940 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 5 ms 14936 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 5 ms 15452 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 6 ms 14940 KB Output is correct
10 Correct 6 ms 14940 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 5 ms 14940 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 5 ms 14940 KB Output is correct
15 Correct 5 ms 15036 KB Output is correct
16 Correct 5 ms 14940 KB Output is correct
17 Correct 5 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 5 ms 15000 KB Output is correct
21 Correct 5 ms 14784 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 5 ms 14940 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct
25 Incorrect 114 ms 21168 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 27344 KB Output is correct
2 Correct 689 ms 28600 KB Output is correct
3 Correct 438 ms 25648 KB Output is correct
4 Correct 681 ms 28588 KB Output is correct
5 Correct 265 ms 21268 KB Output is correct
6 Correct 731 ms 28612 KB Output is correct
7 Correct 565 ms 27336 KB Output is correct
8 Correct 698 ms 29020 KB Output is correct
9 Correct 85 ms 17016 KB Output is correct
10 Correct 676 ms 28660 KB Output is correct
11 Correct 427 ms 23264 KB Output is correct
12 Correct 688 ms 28696 KB Output is correct
13 Correct 455 ms 26816 KB Output is correct
14 Correct 392 ms 26400 KB Output is correct
15 Correct 352 ms 25276 KB Output is correct
16 Correct 390 ms 26044 KB Output is correct
17 Correct 482 ms 27412 KB Output is correct
18 Correct 404 ms 25536 KB Output is correct
19 Correct 406 ms 24864 KB Output is correct
20 Correct 408 ms 25396 KB Output is correct
21 Correct 429 ms 26040 KB Output is correct
22 Correct 408 ms 26044 KB Output is correct
23 Correct 379 ms 25336 KB Output is correct
24 Correct 363 ms 25888 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14940 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 5 ms 14936 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 5 ms 15452 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 6 ms 14940 KB Output is correct
10 Correct 6 ms 14940 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 5 ms 14940 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 5 ms 14940 KB Output is correct
15 Correct 5 ms 15036 KB Output is correct
16 Correct 5 ms 14940 KB Output is correct
17 Correct 5 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 5 ms 15000 KB Output is correct
21 Correct 5 ms 14784 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 5 ms 14940 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct
25 Incorrect 114 ms 21168 KB Output isn't correct
26 Halted 0 ms 0 KB -