Submission #1172395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172395		mateuszwes	Two Antennas (JOI19_antennas)	C++20	22 / 100	106 ms	16132 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()
#define deb(x) if(debug) cout << #x << " = " << x << '\n';

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

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

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

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

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+1];
	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+1,n)].pb(-(i+1));
	}

	if(n <= 2000) base = 1<<10;
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int a1, b1; cin >> a1 >> b1;
		a1--;
		b1--;
		int sc = -1;
		deb(a1);
		deb(b1);

		for(int i = a1; i <= b1; i++){
			for(auto k: flags[i]){
				deb(k);

				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 >= a1){
				int mini = query(max(a1,i-ants[i].b), i-ants[i].a, 0);
				if(mini <= ants[i].h) sc = max(sc, ants[i].h-mini);
				int maxi = query(max(a1,i-ants[i].b), i-ants[i].a, 1);
				if(maxi >= ants[i].h) sc = max(sc, maxi-ants[i].h);
			}

			deb(i);
			deb(sc);
		}
		cout << sc << '\n';
		if(debug) cout << endl;

		for(int i = a1; i <= b1; i++){
			for(auto k: flags[i]){
				if(k > 0){
					update(k-1, M,0);
					update(k-1, -M,1);
				}
				else{
					update(-(k+1), M,0);
					update(-(k+1), -M,1);
				}
			}
		}
		
	}


	return 0;
}

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