제출 #103981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103981		IOrtroiii	Two Antennas (JOI19_antennas)	C++14	100 / 100	1348 ms	48724 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;
const int inf = 1e9;

int n, q;
int a[N], from[N], to[N];
int L[N], R[N], ans[N];

int mx[N << 2];
int sub[N << 2];
int lz[N << 2];

vector<int> toadd[N];
vector<int> todel[N];
vector<int> toget[N];

#define md ((l + r) >> 1)

void push(int v,int l,int r) {
	if (lz[v] < inf) {
		sub[v] = max(sub[v], mx[v] - lz[v]);
		if (l < r) {
			lz[v << 1] = min(lz[v << 1], lz[v]);
			lz[v << 1 | 1] = min(lz[v << 1 | 1], lz[v]);
		}
		lz[v] = inf;
	}
}

void pull(int v) {
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	sub[v] = max(sub[v << 1], sub[v << 1 | 1]);
}

void upd(int v,int l,int r,int pos,int val) {
	push(v, l, r);
	if (l > pos || r < pos) return;
	if (l == r) {
		mx[v] = val;
		return;
	}
	upd(v << 1, l, md, pos, val);
	upd(v << 1 | 1, md + 1, r, pos, val);
	pull(v);
}

void upd(int v,int l,int r,int L,int R,int val) {
	push(v, l, r);
	if (L > r || R < l) return;
	if (L <= l && r <= R) {
		lz[v] = val;
		push(v, l, r);
		return;
	}
	upd(v << 1, l, md, L, R, val);
	upd(v << 1 | 1, md + 1, r, L, R, val);
	pull(v);
}

int get(int v,int l,int r,int L,int R) {
	push(v, l, r);
	if (L > r || R < l) return -1;
	if (L <= l && r <= R) return sub[v];
	return max(get(v << 1, l, md, L, R), get(v << 1 | 1, md + 1, r, L, R));
}

void go() {
	for (int v = 1; v <= (n << 2); ++v) {
		mx[v] = 0;
		sub[v] = -1;
		lz[v] = inf;
	}
	for (int i = 1; i <= n; ++i) {
		toadd[i].clear();
		todel[i].clear();
		toget[i].clear();
	}
	for (int i = 1; i <= q; ++i) {
		toget[R[i]].push_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		if (i + from[i] <= n) toadd[i + from[i]].push_back(i);
		if (i + to[i] <= n) todel[i + to[i]].push_back(i);
		for (int id : toadd[i]) upd(1, 1, n, id, a[id]);
		if (i > from[i]) upd(1, 1, n, max(1, i - to[i]), i - from[i], a[i]);
		for (int id : toget[i]) ans[id] = max(ans[id], get(1, 1, n, L[id], R[id]));
		for (int id : todel[i]) upd(1, 1, n, id, 0);
	}
}

int main() {
	scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d %d", a + i, from + i, to + i);
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    ans[i] = -1;
    scanf("%d %d", L + i, R + i);
  }
  go();
  reverse(a + 1, a + 1 + n);
  reverse(from + 1, from + 1 + n);
  reverse(to + 1, to + 1 + n);
  for (int i = 1; i <= q; ++i) {
    L[i] = n + 1 - L[i];
    R[i] = n + 1 - R[i];
    swap(L[i], R[i]);
  }
  go();
  for (int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i]);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'int main()':
antennas.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", a + i, from + i, to + i);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
antennas.cpp:102:10: 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