Submission #1172380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172380		mateuszwes	Two Antennas (JOI19_antennas)	C++20	0 / 100	93 ms	15460 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define ull unsigned ll
#define pq priority_queue
#define pb push_back
#define all(x) x.begin(), x.end()

constexpr int base = 1 << 18;
constexpr int N = (base<<1) + 7;
constexpr int M = 1e9+7;
int n;
int sq;

int tree[N][2];				//0 to mintree, 1 to maxtree

struct ant{
	int a, b, h;
};

struct que{
	int a, b, ind, ans;
};

bool mosort(que a, que b){
	if(a.a/sq == b.a/sq) return a.b < b.b;
	return a.a/sq < b.a/sq;
}

bool indsort(que a, que b){
	return a.ind < b.ind;
}

int query(int a, int b, int typ){
	int ans;
	typ ? ans = -M : ans = M;
	a += base-1;
	b += base+1;
	while(a>>1 != b>>1){
		if(!(a&1)){
			typ ? ans = max(ans, tree[a+1][typ]) : ans = min(ans, tree[a+1][typ]);
		}
		if(b&1){
			typ ? ans = max(ans, tree[b-1][typ]) : ans = min(ans, tree[b-1][typ]);
		}
		a >>= 1; b >>= 1;
	}
	return ans;
}

void update(int v, int val, int typ){
	v += base;
	tree[v][typ] = val;
	while(v >>= 1){
		typ ? tree[v][typ] = max(tree[v<<1][typ],tree[v<<1|1][typ]) : tree[v][typ] = min(tree[v<<1][typ],tree[v<<1|1][typ]);
	}
}

vector<ant> ants;
vector<que> ques;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < N; i++){
		tree[i][0] = M;
		tree[i][1] = -M;
	}

	cin >> n;
	ants.resize(n);
	vector<int> flags[n];
	for(int i = 0; i < n; i++){
		cin >> ants[i].h >> ants[i].a >> ants[i].b;
		flags[min(i+ants[i].a,n-1)].pb(i+1);
		flags[min(i+ants[i].b,n-1)].pb(-(i+1));
	}
	int q; cin >> q;
	ques.resize(q);
	for(int i = 0; i < q; i++){
		cin >> ques[i].a >> ques[i].b;
		ques[i].ind = i;
	}

	int sc = -1;
	for(int i = 0; i < n; i++){
		for(auto k: flags[i]){
			if(k > 0){
				update(k-1, ants[k-1].h,0);
				update(k-1, ants[k-1].h,1);
			}
			else{
				update(k-1, M,0);
				update(k-1, -M,1);
			}
		}

		if(i-ants[i].a >= 0){
			int mini = query(max(0,i-ants[i].b), i-ants[i].a, 0);
			if(mini <= ants[i].h) sc = max(sc, ants[i].h-mini);
		}
		if(i+ants[i].a < n){
			int maxi = query(ants[i].a, min(n-1,i+ants[i].b),1);
			if(maxi >= ants[i].h) sc = max(sc, maxi-ants[i].h);
		}
	}
	cout << sc << '\n';

	return 0;
}

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