제출 #123738

#제출 시각아이디문제언어결과실행 시간메모리
123738aintaTwo Antennas (JOI19_antennas)C++17
100 / 100
906 ms34076 KiB
#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]); } }

컴파일 시 표준 에러 (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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...