Submission #1008390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008390		PoPularPlusPlus	Two Antennas (JOI19_antennas)	C++17	0 / 100	681 ms	524288 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Seg {
	vector<int> mx,mn;
	int siz;

	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;

		mx.assign(siz * 2 , -1);
		mn.assign(siz * 2 , 1e9);
	}

	void set(int i , int mx_val , int mn_val , int x , int lx , int rx){
		if(rx - lx == 1){
			mx[x] = mx_val;
			mn[x] = mn_val;
			return;
		}
		int m = (lx + rx)/2;
		if(i < m)set(i , mx_val , mn_val , 2 * x + 1 , lx , m);
		else set(i , mx_val , mn_val , 2 * x + 2 , m , rx);

		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
		mn[x] = min(mn[2 * x + 1] , mn[2 * x + 2]);
	}

	void set(int i , int mx_val , int mn_val){
		set(i , mx_val , mn_val , 0 , 0 , siz);
	}

	pair<int,int> range(int l , int r , int x , int lx, int rx){
		if(r >= lx || rx >= l)return mp(-1,1e9);
		if(lx >= l && rx <= r)return mp(mx[x] , mn[x]);
		int m = (lx + rx)/2;
		pair<int,int> p1 = range(l , r , 2 * x + 1 , lx , m), p2 = range(l , r , 2 * x + 2 , m , rx);
		return mp(max(p1.vf , p2.vf) , min(p1.vs , p2.vs));
	}

	pair<int,int> range(int l , int r){
		return range(l , r , 0 , 0 , siz);
	}
};

struct SegMx {
	vector<int> mx;
	int siz;

	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;

		mx.assign(siz * 2 , -1);
	}

	void build(vector<int>& a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < a.size()){
				mx[x] = a[lx];
			}
			return;
		}
		int m = (lx + rx)/2;
		build(a , 2 * x + 1 , lx , m);
		build(a , 2 * x + 2 , m , rx);
		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
	}

	void build(vector<int>& a){
		build(a , 0 , 0 ,siz);
	}

	int range(int l , int r , int x , int lx, int rx){
		if(r >= lx || rx >= l)return -1;
		if(lx >= l && rx <= r)return mx[x];
		int m = (lx + rx)/2;
		return max(range(l , r , 2 * x + 1 , lx , m), range(l , r , 2 * x + 2 , m , rx));
	}

	int range(int l , int r){
		return range(l , r , 0 , 0 , siz);
	}
};

int block;

void solve(){
	int n;
	cin >> n;
	int h[n];
	int a[n] , b[n];
	for(int i = 0; i < n; i++){
		cin >> h[i] >> a[i] >> b[i];
	}

	block = max(2 , (int)sqrt(n));

	vector<pair<int,int>> st;
	int block_num[n];
	int cur = 0;
	for(int i = 0; i < n; i += block){
		st.pb(mp(i , min(n -1 , i + block - 1)));
		for(int j = st.back().vf; j <= st.back().vs; j++){
			block_num[j] = cur;
		}
		cur++;
	}

	Seg segtree;
	segtree.init(n);

	vector<int> off[n + 1];
	int pre[n][st.size()];
	memset(pre,-1,sizeof pre);
	for(int i = 0; i < n; i++){
		off[min(i + b[i] , n)].pb(i);
		for(int j : off[i]){
			segtree.set(j , -1 , 1e9);
		}
		for(int j = block_num[i]; j >= 0; j--){
			int dis = i - st[j].vf;
			if(dis > a[i]){
				if(j == block_num[i]){
					pre[i][j] = -1;
				}
				else {
					pre[i][j] = pre[i][j+1];
				}
			}
			else {
				pair<int,int> p = segtree.range(st[j].vf , i);
				int small = p.vf;
				int big = p.vs;
				pre[i][j] = max(h[i] - small , big - h[i]);
				if(j != block_num[i])pre[i][j] = max(pre[i][j] , pre[i][j + 1]);
			}
		}
	}

	SegMx stmx[st.size()];
	for(int i = 0; i < st.size(); i++){
		stmx[i].init(n);
		vector<int> temp;
		for(int j = 0; j < n; j++){
			temp.pb(pre[j][i]);
		}
		stmx[i].build(temp);
	}

	int q;
	cin >> q;
	int ans[q];
	memset(ans,-1,sizeof ans);
	vector<int> find[n];
	int right[q];
	for(int tp = 0; tp < q; tp++){
		int l , r;
		cin >> l >> r;
		l--;
		r--;
		right[tp] = r;
		int bl = block_num[l] + 1;
		if(st[bl].vf < r){
			ans[tp] = stmx[bl].range(st[bl].vf , r + 1);
		}
		for(int i = l; i <= min(st[block_num[l]].vs,r); i++){
			find[i].pb(tp);
		}
	}

	segtree.init(n);

	for(int i = n - 1; i >= 0; i--){
		for(int j : find[i]){
			if(right[j] > i){
				pair<int,int> p = segtree.range(i , right[j] + 1);
				int small = p.vf;
				int big = p.vs;
				ans[j] = max({ans[j] , h[i] - small , big - h[i]});
			}
		}
	}

	for(int i = 0; i < q; i++){
		cout << ans[i] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//int t;
	//cin >> t;
	//while(t--)
		solve();
}

Compilation message (stderr)

antennas.cpp: In member function 'void SegMx::build(std::vector<int>&, int, int, int)':
antennas.cpp:69:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    if(lx < a.size()){
      |       ~~~^~~~~~~~~~
antennas.cpp: In function 'void solve()':
antennas.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int i = 0; i < st.size(); i++){
      |                 ~~^~~~~~~~~~~

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