제출 #123464

#제출 시각아이디문제언어결과실행 시간메모리
123464imyujinTwo Antennas (JOI19_antennas)C++14
0 / 100
499 ms50684 KiB
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; #define MAXN 200005 const int INF = 1 << 30; int N, Q; int H[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN]; int ans[MAXN]; int minc[4*MAXN], maxd[4*MAXN], lazy[4*MAXN]; vector<int> query[MAXN], on[2*MAXN], off[2*MAXN]; void spreadlazy(int idx) { if(lazy[idx] != -1) { lazy[idx * 2] = lazy[idx * 2 + 1] = lazy[idx]; maxd[idx * 2] = max(maxd[idx * 2], lazy[idx] - minc[idx * 2]); maxd[idx * 2 + 1] = max(maxd[idx * 2 + 1], lazy[idx] - minc[idx * 2 + 1]); lazy[idx] = -1; } } void updc(int idx, int l, int r, int x, int c) { //if(idx == 1) printf("updc(x = %d, c = %d)\n", x, c); if(l == r) { minc[idx] = c; maxd[idx] = max(maxd[idx], lazy[idx] - c); return; } spreadlazy(idx); int m = (l + r) / 2; if(x <= m) updc(idx * 2, l, m, x, c); else updc(idx * 2 + 1, m + 1, r, x, c); minc[idx] = min(minc[idx * 2], minc[idx * 2 + 1]); maxd[idx] = max(maxd[idx * 2], maxd[idx * 2 + 1]); } void updlazy(int idx, int l, int r, int x, int y, int z) { //if(idx == 1) printf("updlazy(x = %d, y = %d, z = %d)\n", x, y, z); if(x <= l && r <= y) { lazy[idx] = z; maxd[idx] = max(maxd[idx], z - minc[idx]); if(l < r) spreadlazy(idx); return; } if(r < x || y < l) return; spreadlazy(idx); int m = (l + r) / 2; updlazy(idx * 2, l, m, x, y, z); updlazy(idx * 2 + 1, m + 1, r, x, y, z); maxd[idx] = max(maxd[idx * 2], maxd[idx * 2 + 1]); } int gmaxd(int idx, int l, int r, int x, int y) { if(x <= l && r <= y) return maxd[idx]; if(r < x || y < l) return -1; int m = (l + r) / 2; spreadlazy(idx); return max(gmaxd(idx * 2, l, m, x, y), gmaxd(idx * 2 + 1, m + 1, r, x, y)); } void print(int x){ printf("#%d\n", x); for(int i = 1; i < 10; i++) printf("i = %d, maxd = %d, minc = %d, lazy = %d\n", i, maxd[i], minc[i], lazy[i]); for(int i = 0; i < Q; i++) printf("ans[%d] = %d\n", i, ans[i]); printf("\n"); } void solve() { for(int i = 0; i < 2 * N; i++) { query[i].clear(); on[i].clear(); off[i].clear(); } for(int i = 0; i < Q; i++) query[R[i]].push_back(i); for(int i = 0; i < N; i++) { on[i + A[i]].push_back(i); off[i + B[i]].push_back(i); } for(int i = 1; i < 4 * N; i++) { minc[i] = INF; maxd[i] = lazy[i] = -1; } for(int i = 0; i < N; i++) { for(auto a : on[i]) updc(1, 0, N-1, a, H[a]); //print(1); updlazy(1, 0, N-1, i - B[i], i - A[i], H[i]); //print(2); for(auto a : query[i]) ans[a] = max(ans[a], gmaxd(1, 0, N-1, L[a], i)); //print(3); for(auto a : off[i]) updc(1, 0, N-1, a, INF); //print(4); } } int main() { scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i); scanf("%d", &Q); for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i); for(int i = 0; i < Q; i++) { ans[i] = -1; L[i]--; R[i]--; } solve(); for(int i = 0; i < N/2; i++){ swap(H[i], H[N - i - 1]); swap(A[i], A[N - i - 1]); swap(B[i], B[N - i - 1]); } for(int i = 0; i < Q; i++) { swap(L[i], R[i]); L[i] = N - L[i] - 1; R[i] = N - R[i] - 1; } solve(); for(int i = 0; i < Q; i++) printf("%d\n", ans[i]); return 0; }

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

antennas.cpp: In function 'int main()':
antennas.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:103:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:105:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
                             ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...