Submission #123899

#	Time	Username	Problem	Language	Result	Execution time	Memory
123899		sebinkim	Two Antennas (JOI19_antennas)	C++14	100 / 100	860 ms	39432 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

struct segtree{
	int T[606060], L[606060], C[606060];
	
	void spread(int p)
	{
		L[p << 1] = max(L[p << 1], L[p]);
		T[p << 1] = max(T[p << 1], L[p << 1] - C[p << 1]);
		L[p << 1 | 1] = max(L[p << 1 | 1], L[p]);
		T[p << 1 | 1] = max(T[p << 1 | 1], L[p << 1 | 1] - C[p << 1 | 1]);
		L[p] = 0;
	}
	
	void update(int p)
	{
		C[p] = min(C[p << 1], C[p << 1 | 1]);
		T[p] = max(T[p << 1], T[p << 1 | 1]);
	}
	
	void init(int p, int s, int e)
	{
		T[p] = -1e9, L[p] = 0, C[p] = 2e9;
		if(s != e){
			init(p << 1, s, s + e >> 1);
			init(p << 1 | 1, (s + e >> 1) + 1, e);
		}
	}
	
	void update1(int p, int s, int e, int v, int c)
	{
		if(s == e) L[p] = 0, C[p] = c;
		else{
			spread(p);
			if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
			else update1(p << 1 | 1, (s + e >> 1) + 1, e, v, c);
			update(p);
		}
	}
	
	void update2(int p, int s, int e, int l, int r, int c)
	{
		if(e < l || r < s) return;
		else if(l <= s && e <= r){
			L[p] = max(L[p], c);
			T[p] = max(T[p], L[p] - C[p]);
			return;
		}
		
		spread(p);
		update2(p << 1, s, s + e >> 1, l, r, c);
		update2(p << 1 | 1, (s + e >> 1) + 1, e, l, r, c);
		update(p);
	}
	
	int getmax(int p, int s, int e, int l, int r)
	{
		if(e < l || r < s) return -1e9;
		else if(l <= s && e <= r) return T[p];
		
		spread(p);
		int ret = getmax(p << 1, s, s + e >> 1, l, r);
		ret = max(ret, getmax(p << 1 | 1, (s + e >> 1) + 1, e, l, r));
		update(p);
		
		return ret;
	}
};

segtree T;
vector <int> V[202020], Q[202020];
int H[202020], A[201010], B[202020];
int L[202020], R[202020], X[202020];
int n, q;

void f()
{
	int i;
	
	T.init(1, 1, n);
	
	for(i=1; i<=n; i++){
		V[i].clear(); Q[i].clear();
	}
	
	for(i=1; i<=q; i++){
		Q[R[i]].push_back(i);
	}
	
	for(i=1; i<=n; i++){
		if(i + A[i] <= n) V[i + A[i]].push_back(i);
		if(i + B[i] < n) V[i + B[i] + 1].push_back(-i);
		
		for(int &t: V[i]){
			if(t > 0) T.update1(1, 1, n, t, H[t]);
			else T.update1(1, 1, n, -t, 2e9);
		}
		
		if(i - A[i] >= 1){
			T.update2(1, 1, n, max(1, i - B[i]), i - A[i], H[i]);
		}
		
		for(int &t: Q[i]){
			X[t] = max(X[t], T.getmax(1, 1, n, L[t], i));
		}
	}
}

int main()
{
	int i;
	
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		scanf("%d%d%d", H + i, A + i, B + i);
	}
	
	scanf("%d", &q);
	
	for(i=1; i<=q; i++){
		scanf("%d%d", L + i, R + i);
		X[i] = -1;
	}
	
	f();
	
	reverse(H + 1, H + n + 1);
	reverse(A + 1, A + n + 1);
	reverse(B + 1, B + n + 1);
	
	for(i=1; i<=q; i++){
		L[i] = n + 1 - L[i];
		R[i] = n + 1 - R[i];
		swap(L[i], R[i]);
	}
	
	f();
	
	for(i=1; i<=q; i++){
		printf("%d\n", X[i]);
	}
	
	return 0;
}

Compilation message (stderr)

antennas.cpp: In member function 'void segtree::init(int, int, int)':
antennas.cpp:27:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    init(p << 1, s, s + e >> 1);
                    ~~^~~
antennas.cpp:28:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    init(p << 1 | 1, (s + e >> 1) + 1, e);
                      ~~^~~
antennas.cpp: In member function 'void segtree::update1(int, int, int, int, int)':
antennas.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
             ~~^~~
antennas.cpp:37:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
                                             ~~^~~
antennas.cpp:38:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    else update1(p << 1 | 1, (s + e >> 1) + 1, e, v, c);
                              ~~^~~
antennas.cpp: In member function 'void segtree::update2(int, int, int, int, int, int)':
antennas.cpp:53:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update2(p << 1, s, s + e >> 1, l, r, c);
                      ~~^~~
antennas.cpp:54:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update2(p << 1 | 1, (s + e >> 1) + 1, e, l, r, c);
                        ~~^~~
antennas.cpp: In member function 'int segtree::getmax(int, int, int, int, int)':
antennas.cpp:64:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int ret = getmax(p << 1, s, s + e >> 1, l, r);
                               ~~^~~
antennas.cpp:65:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ret = max(ret, getmax(p << 1 | 1, (s + e >> 1) + 1, e, l, r));
                                      ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:118: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:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:124: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