Submission #173672

#	Time	Username	Problem	Language	Result	Execution time	Memory
173672		ZwariowanyMarcin	Two Antennas (JOI19_antennas)	C++14	100 / 100	846 ms	37872 KiB

antennas

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;
const int pod = (1 << 18);
const long long INF = 1e17;

int n;
int h[nax];
int a[nax];
int b[nax];
int q;
ll ans[nax];
int l[nax];
int r[nax];

struct gao {
	int type, x;
};
// 0 - akt 
// 1 - query[x]

vector <gao> v[nax];

struct seg {
	struct nod {
		ll best, val, mini;
		nod () {}
		nod (ll b, ll v, ll m) : best(b), val(v), mini(m) {}
	};
	nod t[2 * pod];
	
	void init() {
		for(int i = 1; i < 2 * pod; ++i) 
			t[i] = nod(-INF, -INF, INF);
	}
	
	void make(int u) {
		t[u].best = max(t[2 * u].best, t[2 * u + 1].best);
		t[u].mini = min(t[2 * u].mini, t[2 * u + 1].mini);
	}
	
	void push(int u) {
		if(t[u].val == -INF) return;
		t[2 * u].val = max(t[2 * u].val, t[u].val);
		t[2 * u + 1].val = max(t[2 * u + 1].val, t[u].val);
		t[2 * u].best = max(t[2 * u].best, t[u].val - t[2 * u].mini);
		t[2 * u + 1].best = max(t[2 * u + 1].best, t[u].val - t[2 * u + 1].mini);
		t[u].val = -INF;
	}
	
	void akt(int x, int u = 1, int l = 0, int r = pod - 1) {
		if(l == r) {
			if(t[u].mini == INF) 
				t[u].mini = h[l];
			else 
				t[u].mini = INF;
			return;
		}
		push(u);
		int m = (l + r) / 2;
		if(x <= m) akt(x, 2 * u, l, m);
		else akt(x, 2 * u + 1, m + 1, r);
		make(u);
	}
	
	void zmaxuj(int x, int y, ll z, int u = 1, int l = 0, int r = pod - 1) {
		if(x <= l && r <= y) {
			t[u].best = max(t[u].best, z - t[u].mini);
			t[u].val = max(t[u].val, z);
			return;
		}
		push(u);
		int m = (l + r) / 2;
		if(x <= m) zmaxuj(x, y, z, 2 * u, l, m);
		if(m < y) zmaxuj(x, y, z, 2 * u + 1, m + 1, r);
		make(u);
	}
	
	ll query(int x, int y, int u = 1, int l = 0, int r = pod - 1) {
		if(x <= l && r <= y) return t[u].best;
		push(u);
		int m = (l + r) / 2;
		ll best = -INF;
		if(x <= m) best = query(x, y, 2 * u, l, m);
		if(m < y) best = max(best, query(x, y, 2 * u + 1, m + 1, r));
		return best;
	}
} ja;

void solve() {
	ja.init();
	for(int i = 1; i <= n; ++i)
		v[i].clear();
	for(int i = 1; i <= n; ++i) {
		int A = i + a[i];
		int B = i + b[i] + 1;
		if(A <= n)
			v[A].pb({0, i});
		if(B <= n)
			v[B].pb({0, i});
	}
	
	for(int i = 1; i <= q; ++i)
		v[r[i]].pb({1, i});
	
	for(int i = 1; i <= n; ++i) {
		
		int wsk = 0;
		while(wsk < ss(v[i]) && v[i][wsk].type == 0) {
			ja.akt(v[i][wsk].x);
		//	printf("akt %d %d\n", v[i][wsk].x, i);
			wsk++;
		}
		
		int L = max(1, i - b[i]);
		int R = i - a[i];
	//	printf("zmax %d %d\n", L, R);
		if(L <= R)
			ja.zmaxuj(L, R, h[i]);
		
		while(wsk < ss(v[i])) {
		//	printf("%d %d\n", i, v[i][wsk].x);
			ans[v[i][wsk].x] = max(ans[v[i][wsk].x], ja.query(l[v[i][wsk].x], i - 1));
			wsk++;
		}
	}
}
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) 
		scanf("%d %d %d", h + i, a + i, b + i);
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) 
		scanf("%d %d", l + i, r + i);
	for(int i = 1; i <= q; ++i)
		ans[i] = -1;
	solve();
	for(int i = 1; i <= n; ++i)
		h[i] *= -1;
	solve();
	for(int i = 1; i <= q; ++i) {
		ans[i] = max(ans[i], -1ll);
		printf("%lld\n", ans[i]);
	}
	
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:142: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:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:145: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