Submission #259098

#	Time	Username	Problem	Language	Result	Execution time	Memory
259098		patrikpavic2	Two Antennas (JOI19_antennas)	C++17	100 / 100	782 ms	41080 KiB

antennas

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int OFF = (1 << 18);
const int N = 2e5 + 500;

pii T[2 * OFF], P[2 * OFF], NULA = {-1, -1};
int sol[2 * OFF], uklj[2 * OFF], L[N], R[N], A[N], B[N], H[N], ans[N], n, q;
vector < int > Q[N], prom[N];

inline pii spoji_par(pii A, pii B){
	if(A == NULA) return B;
	if(B == NULA) return A;
	return {min(A.X, B.X), max(A.Y, B.Y)};
}

void refresh(int x){
	if(P[x] == NULA) return;
	if(T[x] != NULA){
		sol[x] = max(sol[x], max(T[x].Y - P[x].X, P[x].Y - T[x].X));
		if(x < OFF){
			P[2 * x] = spoji_par(P[2 * x], P[x]);
			P[2 * x + 1] = spoji_par(P[2 * x + 1], P[x]);
		}
	}
	P[x] = NULA;
}

inline void spoji_u(int i){
	T[i] = spoji_par(T[2 * i], T[2 * i + 1]);
	sol[i] = max(sol[2 * i], sol[2 * i + 1]);
}

void promijeni(int i,int a,int b,int tko){
	refresh(i);
	if(a == b){
		uklj[tko] = !uklj[tko];
		if(uklj[tko])
			T[i] = {H[tko], H[tko]};
		else
			T[i] = NULA; 
		return;
	}	
	if(tko <= (a + b) / 2)
		promijeni(2 * i, a, (a + b) / 2, tko);
	else
		promijeni(2 * i + 1, (a + b) / 2 + 1, b, tko);
	refresh(2 * i); refresh(2 * i + 1);
	spoji_u(i);
}

void dodaj(int i, int a, int b, int lo, int hi, int nov){
	refresh(i);
	if(lo <= a && b <= hi){
		P[i] = spoji_par(P[i], {nov, nov});
		refresh(i); return;
	}
	if(a > hi || b < lo) return;
	dodaj(2 * i, a, (a + b) / 2, lo, hi, nov);
	dodaj(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, nov);
	spoji_u(i);
}

int query(int i,int a,int b,int lo,int hi){
	refresh(i);
	if(lo <= a && b <= hi) return sol[i];
	if(a > hi || b < lo) return -1;
	return max(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}


int main(){
	for(int i = 0;i < 2 * OFF;i++)
		T[i] = NULA, P[i] = NULA, sol[i] = -1;
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d%d", H + i, A + i, B + i);
		if(i + A[i] <= n){
			prom[i + A[i]].PB(i);
			if(i + B[i] + 1 <= n)
				prom[i + B[i] + 1].PB(i);
		}
	}
	scanf("%d", &q);
	for(int i = 1;i <= q;i++){
		scanf("%d%d", L + i, R + i);
		Q[R[i]].PB(i);
	}
	for(int i = 1;i <= n;i++){
		for(int x : prom[i])
			promijeni(1, 0, OFF - 1, x);
		dodaj(1, 0, OFF - 1, max(i - B[i], 1), max(i - A[i], 0), H[i]);
		for(int c : Q[i])
			ans[c] = query(1, 0, OFF - 1, L[c], R[c]);
	}
	for(int i = 1;i <= q;i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

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