Submission #123738

#	Time	Username	Problem	Language	Result	Execution time	Memory
123738		ainta	Two Antennas (JOI19_antennas)	C++17	100 / 100	906 ms	34076 KiB

antennas

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define pii pair<int,int>
#define SZ 262144
int n, Q, Res[201000], INF = 1e9+123;
struct point {
	int h, a, b;
}w[201000];
struct Query {
	int b, e;
}QQ[201000];
vector<pii>G[201000], A[201000];

struct Tree {
	int Mx[SZ + SZ], MnC[SZ + SZ], MxH[SZ + SZ];
	void init() {
		for (int i = 0; i < SZ + SZ; i++) {
			Mx[i] = -INF;
			MxH[i] = -INF;
			MnC[i] = INF;
		}
	}
	void Spread(int nd) {
		Mx[nd * 2] = max(Mx[nd * 2], MxH[nd] - MnC[nd * 2]);
		MxH[nd * 2] = max(MxH[nd * 2], MxH[nd]);
		Mx[nd * 2 + 1] = max(Mx[nd * 2 + 1], MxH[nd] - MnC[nd * 2 + 1]);
		MxH[nd * 2 + 1] = max(MxH[nd * 2 + 1], MxH[nd]);
		Mx[nd] = max(Mx[nd], max(Mx[nd * 2], Mx[nd * 2 + 1]));
		MxH[nd] = -INF;
	}
	void UDT(int nd) {
		MnC[nd] = min(MnC[nd * 2], MnC[nd * 2 + 1]);
		Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
	}
	void PutC(int nd, int b, int e, int x, int c) {
		if (b == e) {
			MnC[nd] = c;
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (x <= m)PutC(nd * 2, b, m, x, c);
		else PutC(nd * 2 + 1, m + 1, e, x, c);
		UDT(nd);
	}
	void Do(int nd, int b, int e, int s, int l, int h) {
		if (s > l)return;
		if (s <= b && e <= l) {
			if(b!=e) Spread(nd);
			MxH[nd] = h;
			Mx[nd] = max(Mx[nd], h - MnC[nd]);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Do(nd * 2, b, m, s, l, h);
		if(l > m) Do(nd * 2 + 1, m + 1, e, s, l, h);
		UDT(nd);
	}
	int Get(int nd, int b, int e, int s, int l) {
		if (s > l)return -INF;
		if (s <= b && e <= l)return Mx[nd];
		Spread(nd);
		int m = (b + e) >> 1, r = -INF;
		if (s <= m)r = max(r, Get(nd * 2, b, m, s, l));
		if (l > m) r = max(r, Get(nd * 2 + 1, m + 1, e, s, l));
		UDT(nd);
		return r;
	}
}T;

void Solve() {
	int i;
	for (i = 1; i <= n; i++) {
		G[i].clear();
		A[i].clear();
	}
	T.init();
	for (i = 1; i <= Q; i++) {
		G[QQ[i].e].push_back({ QQ[i].b,i });
	}
	for (i = 1; i <= n; i++) {
		int b = i + w[i].a;
		int e = min(i + w[i].b, n);
		if (b > e)continue;
		A[b].push_back({ i,1 });
		A[e + 1].push_back({ i,-1 });
	}
	for (i = 1; i <= n; i++) {
		for (auto &t : A[i]) {
			if (t.second == 1)T.PutC(1, 1, n, t.first, w[t.first].h);
			else T.PutC(1, 1, n, t.first, INF);
		}
		int b = max(i - w[i].b, 1), e = i - w[i].a;
		if (b <= e) T.Do(1, 1, n, b, e, w[i].h);
		for (auto &t : G[i]) {
			int b = t.first;
			Res[t.second] = max(Res[t.second], T.Get(1, 1, n, b, i - 1));
		}
	}
}

int main() {
	int i, j, k;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
	}
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		Res[i] = -1;
		scanf("%d%d", &QQ[i].b, &QQ[i].e);
	}
	Solve();
	reverse(w + 1, w + n + 1);
	for (i = 1; i <= Q; i++) {
		int b = QQ[i].b, e = QQ[i].e;
		QQ[i].b = n - e + 1, QQ[i].e = n - b + 1;
	}
	Solve();
	for (i = 1; i <= Q; i++) {
		printf("%d\n", Res[i]);
	}
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:106:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
antennas.cpp:106:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
antennas.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &QQ[i].b, &QQ[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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