Submission #104680

#	Time	Username	Problem	Language	Result	Execution time	Memory
104680		tincamatei	Two Antennas (JOI19_antennas)	C++14	100 / 100	1292 ms	44472 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;
const int MAX_Q = 200000;
const int INF = 1000000001;

int ainta[1+4*MAX_N], aintb[1+4*MAX_N], lazy[1+4*MAX_N];

void updateB(int poz, int val, int l, int r, int nod = 1) {
	if(poz < l || r < poz || r < l) return;

	if(l == r)
		aintb[nod] = val;
	else {
		int mid = (l + r) / 2;
		updateB(poz, val, l, mid, 2 * nod);
		updateB(poz, val, mid + 1, r, 2 * nod + 1);
		aintb[nod] = min(aintb[2 * nod], aintb[2 * nod + 1]);
	}
}

void propagate(int nod, int l, int r) {
	ainta[nod] = max(ainta[nod], lazy[nod] - aintb[nod]);
	if(l < r) {
		lazy[2 * nod] = max(lazy[nod], lazy[2 * nod]);
		lazy[2 * nod + 1] = max(lazy[nod], lazy[2 *  nod + 1]);
	}
	lazy[nod] = 0;
}

void updateA(int i, int j, int val, int l, int r, int nod = 1) {
	propagate(nod, l, r);
	if(j < l || r < i || j < i) return;

	if(i <= l && r <= j) {
		lazy[nod] = max(lazy[nod], val);
		propagate(nod, l, r);
	} else {
		int mid = (l + r) / 2;
		updateA(i, j, val, l, mid, 2 * nod);
		updateA(i, j, val, mid + 1, r, 2 * nod + 1);
		ainta[nod] = max(ainta[2 * nod], ainta[2 * nod + 1]);
	}
}

int queryaint(int i, int j, int l, int r, int nod = 1) {
	propagate(nod, l, r);
	if(r < i || j < l || j < i) return -1;

	if(i <= l && r <= j)
		return ainta[nod];
	else {
		int mid = (l + r) / 2;
		return max(queryaint(i, j, l, mid, 2 * nod),
		           queryaint(i, j, mid + 1, r, 2 * nod + 1));
	}
}

void init(int nod, int l, int r) {
	ainta[nod] = -1;
	aintb[nod] = INF;
	lazy[nod] = 0;

	if(l < r) {
		int mid = (l + r) / 2;
		init(2 * nod, l, mid);
		init(2 * nod + 1, mid + 1, r);
	}
}

struct Tower {
	int h, l, r;
} v[MAX_N];

struct Query {
	int l, r;
	int *rez;
} query[MAX_Q];

int rez[1+MAX_Q];

struct Update {
	int poz, val;
};

vector<Update> updates[MAX_N+1];
vector<Query> queries[MAX_N+1];

void solve(int n, int q) {
	init(1, 0, n - 1);
	
	for(int i = n - 1; i >= 0; --i) {
		updates[i].clear();
		queries[i].clear();

		int st = min(i + v[i].l, n);
		int dr = min(i + v[i].r + 1, n);

		if(st < dr) {
			updates[st].push_back({i, v[i].h});
			updates[dr].push_back({i, INF});
		}
	}

	for(int i = 0; i < q; ++i)
		queries[query[i].r].push_back(query[i]);

	for(int i = 0; i < n; ++i) {
		for(auto it: updates[i]) {
			queryaint(it.poz, it.poz, 0, n - 1);
			updateB(it.poz, it.val, 0, n - 1);
		}

		int st = max(i - v[i].r - 1, -1);
		int dr = max(i - v[i].l, -1);

		if(st < dr)
			updateA(st + 1, dr, v[i].h, 0, n - 1);
	
		for(auto it: queries[i])
			(*it.rez) = max(*it.rez, queryaint(it.l, it.r, 0, n - 1));
	}
}

int main() {
	int n, q;

	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d%d", &v[i].h, &v[i].l, &v[i].r);
	scanf("%d", &q);
	for(int i = 0; i < q; ++i) {
		scanf("%d%d", &query[i].l, &query[i].r);
		query[i].rez = &rez[i];
		rez[i] = -1;
		query[i].l--;
		query[i].r--;
	}

	solve(n, q);

	for(int i = 0; i < q; ++i) {
		query[i].l = n - query[i].l - 1;
		query[i].r = n - query[i].r - 1;
		swap(query[i].l, query[i].r);
	}
	reverse(v, v + n);
	
	solve(n, q);
  
	for(int i = 0; i < q; ++i)
		printf("%d\n", rez[i]);
  
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v[i].h, &v[i].l, &v[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &query[i].l, &query[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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