Submission #260193

#	Time	Username	Problem	Language	Result	Execution time	Memory
260193		mjkocijan	Two Antennas (JOI19_antennas)	C++14	100 / 100	1267 ms	104508 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> ii;
#define X first
#define Y second
#define pb push_back
#define MAXN 800200
#define INF 1001001001

int n, nn = 1 << 18;
int h[MAXN], a[MAXN], b[MAXN];
int q;
int _l[MAXN], _r[MAXN];
int reza[MAXN];

vector<ii> v[MAXN];
vector<int> ad[MAXN], rem[MAXN];
int c[MAXN], d[MAXN], pd[MAXN];

void propaj(int cv)
{
	d[cv] = max(d[cv], c[cv] - pd[cv]);
	if (cv < nn) {
		pd[cv * 2] = min(pd[cv * 2], pd[cv]);
		pd[cv * 2 + 1] = min(pd[cv * 2 + 1], pd[cv]);
	}
	pd[cv] = INF;
}

void setaj(int cv, int lo, int hi, int w, int e)
{
	propaj(cv);

	if (lo > hi || lo > w || hi < w) return;
	
	if (lo == hi) {
		c[cv] = e;
		return;
	}
	
	int mid = (lo + hi) / 2;
	setaj(cv * 2, lo, mid, w, e);
	setaj(cv * 2 + 1, mid + 1, hi, w, e);
	c[cv] = max(c[cv * 2], c[cv * 2 + 1]);
}

void upd(int cv, int lo, int hi, int l, int r, int w)
{
	propaj(cv);
	
	if (lo > hi || lo > r || hi < l) return;
	
	if (lo >= l && hi <= r) {
		pd[cv] = min(pd[cv], w);
		propaj(cv);
		return;
	}
	
	int mid = (lo + hi) / 2;
	upd(cv * 2, lo, mid, l, r, w);
	upd(cv * 2 + 1, mid + 1, hi, l, r, w);
	d[cv] = max(d[cv * 2], d[cv * 2 + 1]);
}

int kveri(int cv, int lo, int hi, int l, int r)
{
	propaj(cv);
	
	if (lo > hi || lo > r || hi < l) return -1;
	
	if (lo >= l && hi <= r) return d[cv];
	
	int mid = (lo + hi) / 2;
	return max(kveri(cv * 2, lo, mid, l, r), kveri(cv * 2 + 1, mid + 1, hi, l, r));
}

void solve()
{
	for (int i = 0; i < q; i++) {
		v[_r[i]].pb({_l[i], i});
	}
	for (int i = 0; i < n; i++) {
		ad[i + a[i]].pb(i);
		rem[i + b[i] + 1].pb(i);
	}
	for (int i = 0; i < n; i++) {
		for (int j: ad[i]) {
			setaj(1, 0, nn - 1, j, h[j]);//cout<<i<<'+'<<j<<endl;
		}
		for (int j: rem[i]) {
			setaj(1, 0, nn - 1, j, -1);//cout<<i<<'-'<<j<<endl;
		}
		
		upd(1, 0, nn - 1, i - b[i], i - a[i], h[i]);//cout<<i-b[i]<<'.'<<i-a[i]<<'.'<<h[i]<<endl;
		
		for (ii j: v[i]) {
			reza[j.Y] = max(reza[j.Y], kveri(1, 0, nn - 1, j.X, i));
		}
	}
}

int main()
{
	memset(reza, -1, sizeof reza);
	memset(c, -1, sizeof c);
	memset(d, -1, sizeof d);
	for (int i = 0; i < MAXN; i++) pd[i] = INF;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &h[i], &a[i], &b[i]);
	}
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d%d", &_l[i], &_r[i]);
		_l[i]--; _r[i]--;
	}
	solve();
	reverse(h, h + n);
	reverse(a, a + n);
	reverse(b, b + n);
	for (int i = 0; i < q; i++) {
		_l[i] = n - 1 - _l[i];
		_r[i] = n - 1 - _r[i];
		swap(_l[i], _r[i]);
	}
	
	for (int i = 0; i < n; i++) {
		v[i].clear();
		ad[i].clear();
		rem[i].clear();
	}
	memset(c, -1, sizeof c);
	memset(d, -1, sizeof d);
	for (int i = 0; i < MAXN; i++) pd[i] = INF;
	solve();
	for (int i = 0; i < q; i++) {
		printf("%d\n", reza[i]);
	}
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &h[i], &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &_l[i], &_r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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