Submission #212540

#	Time	Username	Problem	Language	Result	Execution time	Memory
212540		_7_7_	Two Antennas (JOI19_antennas)	C++14	100 / 100	823 ms	71128 KiB

antennas

#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 3e5 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


vpii g[N];
vi add[N], del[N];
int n, h[N], a[N], b[N], q, l[N], r[N], mx[N << 2], res[N], mxC[N << 2], lz[N << 2];

void push (int v) {
	if (lz[v] < INF) {
		lz[v << 1] = min(lz[v << 1], lz[v]);
		mx[v << 1] = max(mx[v << 1], mxC[v << 1] - lz[v]);

		lz[v << 1 | 1] = min(lz[v << 1 | 1], lz[v]);
		mx[v << 1 | 1] = max(mx[v << 1 | 1], mxC[v << 1 | 1] - lz[v]);
		lz[v] = INF;
	}
}

void upd (int pos, int x, int v = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		lz[v] = INF;
		mxC[v] = x;
		return;
	}

	push(v);
	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		upd(pos, x, v << 1, tl, tm);
	else
		upd(pos, x, v << 1 | 1, tm + 1, tr);

	mxC[v] = max(mxC[v << 1], mxC[v << 1 | 1]);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

void upd1 (int l, int r, int x, int v = 1, int tl = 1, int tr = n) {
	if (l > r || l > tr || tl > r)
		return;

	if (l <= tl && tr <= r) {
		lz[v] = min(lz[v], x);
		mx[v] = max(mx[v], mxC[v] - lz[v]);
		return;
	}

	push(v);
	int tm = (tl + tr) >> 1;
	
	upd1(l, r, x, v << 1, tl, tm);
	upd1(l, r, x, v << 1 | 1, tm + 1, tr);

	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

int get (int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (l > r || l > tr || tl > r)
		return -INF;
	if (l <= tl && tr <= r)
		return mx[v];
	
	push(v);
	int tm = (tl + tr) >> 1;
	return max(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr));
}

void build (int v = 1, int tl = 1, int tr = n) {
	lz[v] = INF;
	mx[v] = mxC[v] = -INF;
	if (tl == tr)	
		return;
	int tm = (tl + tr) >> 1;
	build(v << 1, tl, tm);
	build(v << 1 | 1, tm + 1, tr);
}



void solve () {
	build();
	
	for (int i = 1; i <= n; ++i) {
		add[i].clear();
		del[i].clear();
		g[i].clear();
	}


	for (int i = 1; i <= q; ++i) 
		g[r[i]].pb({l[i], i});
	
	
	for (int i = 1; i <= n; ++i) {
		add[min(n + 1, i + a[i])].pb(i);
		del[min(n + 1, i + b[i] + 1)].pb(i);
	}


	for (int i = 1; i <= n; ++i) {		
		for (auto j : add[i])  {
			upd(j, h[j]);  
//			cerr << j << ' ' << h[j] << endl;
		}
		
		for (auto j : del[i])  {
			upd(j, -INF); 		 
//			cerr << j << ' ' << -INF << endl;
		}

		upd1(max(1ll, i - b[i]), i - a[i], h[i]);
//		cerr << max(1ll, i - b[i]) << ' ' << i - a[i] << ' ' << h[i] << endl;
		for (auto j : g[i])  {
			res[j.s] = max(res[j.s], get(j.f, i)); 
//			cerr << "get " << j.f << ' ' << i << ' ' << get(j.f, i) << endl;
		}
/*
		for (int i = 1; i <= n; ++i)
			cerr << get(i, i) << ' ';
		cerr << endl << endl;*/

	}
//	cerr << endl;
}

main () {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) 
		scanf("%lld%lld%lld", &h[i], &a[i], &b[i]);

	scanf("%lld", &q);	
	for (int i = 1; i <= q; ++i) 
		scanf("%lld%lld", &l[i], &r[i]);

	memset(res, -1, sizeof(res));

	solve();
	for (int i = 1; i <= q; ++i) {
		l[i] = n + 1 - l[i];
		r[i] = n + 1 - r[i];
		swap(l[i], r[i]);
	}


	reverse(h + 1, h + 1 + n);
	reverse(a + 1, a + 1 + n);
	reverse(b + 1, b + 1 + n);
	solve();

	for (int i = 1; i <= q; ++i)
		printf("%lld\n", res[i]);
}

Compilation message (stderr)

antennas.cpp:160:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
antennas.cpp: In function 'int main()':
antennas.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
antennas.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &h[i], &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q); 
  ~~~~~^~~~~~~~~~~~
antennas.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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