oj.uz

Submission #425189

# Submission time Handle Problem Language Result Execution time Memory
425189 2021-06-12T14:55:58 Z Mamnoon_Siam Two Antennas (JOI19_antennas) C++17
100 / 100
 1109 ms 68936 KB 
// https://codeforces.com/blog/entry/66022?#comment-500622

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int inf = 1e9 + 9;

/*struct Node {
  vector<int> c, d;
  Node(int _, int n) {
    c.assign(n, -inf);
    d.assign(n, -inf);
  }
  void update_ci(int pos, int val) {
    c[pos-1] = val;
  }
  void update_di(int L, int R, int val) {
    for(int i = L-1; i < R; ++i) {
      d[i] = max(d[i], c[i] + val);
    }
  }
  int get_max_di(int L, int R) {
    int ret = -inf;
    for(int i = L-1; i < R; ++i) {
      ret = max(ret, d[i]);
    } return ret;
  }
};*/

struct Node {
  Node *l = 0, *r = 0;
  int mx_di = -inf, mx_ci = -inf;
  int lo, hi;
  int lz = -2*inf;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) {
    if(lo < hi) {
      int mid = (lo + hi) >> 1;
      l = new Node(lo, mid);
      r = new Node(mid+1, hi);
    }
  }
  void upd(int val) {
    lz = max(lz, val);
    mx_di = (int)max((ll)mx_di, (ll)mx_ci + lz);
  }
  void push() {
    if(lo < hi) {
      l -> upd(lz);
      r -> upd(lz);
    }
    lz = -2*inf;
  }
  void update_ci(int pos, int ci) {
    if(lo == hi) {
      mx_ci = ci;
      lz = -2*inf;
    } else {
      push();
      if(pos <= l -> hi)
        l -> update_ci(pos, ci);
      else
        r -> update_ci(pos, ci);
      mx_ci = max(l -> mx_ci, r -> mx_ci);
    }
  }
  void update_di(int L, int R, int val) { // do d[i] max= c[i] + val, val negative in this problem
    if(hi < L or lo > R) return;
    if(L <= lo and hi <= R) {
      upd(val);
    } else {
      push();
      l -> update_di(L, R, val);
      r -> update_di(L, R, val);
      mx_di = max(l -> mx_di, r -> mx_di);
    }
  }
  int get_max_di(int L, int R) { // max{ d[i] | i \in [L, R] }
    if(hi < L or lo > R) return -inf;
    if(L <= lo and hi <= R) return mx_di;
    push();
    return max(l->get_max_di(L,R), r->get_max_di(L,R));
  }
};

const int N = 2e5 + 5;

int n, q;
int H[N], A[N], B[N];
int ans[N];
int L[N], R[N];

void solve() {
  vector<vi> offline(n+2), queries_w_R_at(n+1);
  for(int i = 1; i <= q; ++i) {
    queries_w_R_at[R[i]].emplace_back(i);
  }
  for(int i = 1; i <= n; ++i) {
    offline[min(n+1, i + A[i])].emplace_back(i);
    offline[min(n+1, i + B[i] + 1)].emplace_back(-i);
  }
  Node *tr = new Node(1, n);
  for(int i = 1; i <= n; ++i) {
    for(int j : offline[i]) {
      if(j < 0) { // del
        tr -> update_ci(-j, -inf);
      } else { // ins
        tr -> update_ci(j, H[j]);
      }
    }
    if(i - A[i] >= 1) {
      tr -> update_di(max(1, i - B[i]), i - A[i], -H[i]);
    }
    for(int j : queries_w_R_at[i]) {
      ans[j] = max(ans[j], tr -> get_max_di(L[j], R[j]));
    }
  }
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  fill(ans, ans+N, -inf);
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    scanf("%d %d %d", &H[i], &A[i], &B[i]);
  }
  scanf("%d", &q);
  for(int i = 1; i <= q; ++i) {
    scanf("%d %d", &L[i], &R[i]);
  }
  solve();
  for(int i = 1, j = n; i < j; ++i, --j) {
    swap(H[i], H[j]);
    swap(A[i], A[j]);
    swap(B[i], B[j]);
  }
  for(int i = 1; i <= q; ++i) {
    L[i] = n - L[i] + 1;
    R[i] = n - R[i] + 1;
    swap(L[i], R[i]);
  }
  solve();
  for(int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i] < 0 ? -1 : ans[i]);
  }
  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Compilation message

antennas.cpp: In function 'int main(int, const char**)':
antennas.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
antennas.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     scanf("%d %d %d", &H[i], &A[i], &B[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
antennas.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     scanf("%d %d", &L[i], &R[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 15 ms 1092 KB Output is correct
9 Correct 3 ms 1156 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 7 ms 1100 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 2 ms 1096 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 2 ms 1100 KB Output is correct
16 Correct 2 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 14 ms 1092 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 15 ms 1100 KB Output is correct
21 Correct 2 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 2 ms 1100 KB Output is correct
24 Correct 2 ms 1100 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 15 ms 1092 KB Output is correct
9 Correct 3 ms 1156 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 7 ms 1100 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 2 ms 1096 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 2 ms 1100 KB Output is correct
16 Correct 2 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 14 ms 1092 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 15 ms 1100 KB Output is correct
21 Correct 2 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 2 ms 1100 KB Output is correct
24 Correct 2 ms 1100 KB Output is correct
25 Correct 137 ms 5760 KB Output is correct
26 Correct 17 ms 2124 KB Output is correct
27 Correct 216 ms 7784 KB Output is correct
28 Correct 248 ms 7784 KB Output is correct
29 Correct 115 ms 5840 KB Output is correct
30 Correct 136 ms 5776 KB Output is correct
31 Correct 154 ms 6040 KB Output is correct
32 Correct 250 ms 7764 KB Output is correct
33 Correct 191 ms 7492 KB Output is correct
34 Correct 85 ms 4684 KB Output is correct
35 Correct 184 ms 7984 KB Output is correct
36 Correct 217 ms 7752 KB Output is correct
37 Correct 107 ms 4568 KB Output is correct
38 Correct 461 ms 6848 KB Output is correct
39 Correct 27 ms 2372 KB Output is correct
40 Correct 282 ms 6852 KB Output is correct
41 Correct 152 ms 5584 KB Output is correct
42 Correct 214 ms 6800 KB Output is correct
43 Correct 62 ms 3320 KB Output is correct
44 Correct 188 ms 6780 KB Output is correct
45 Correct 37 ms 2548 KB Output is correct
46 Correct 186 ms 6732 KB Output is correct
47 Correct 48 ms 2860 KB Output is correct
48 Correct 246 ms 6748 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 52876 KB Output is correct
2 Correct 634 ms 58824 KB Output is correct
3 Correct 343 ms 41600 KB Output is correct
4 Correct 551 ms 58800 KB Output is correct
5 Correct 192 ms 27528 KB Output is correct
6 Correct 541 ms 58808 KB Output is correct
7 Correct 443 ms 51032 KB Output is correct
8 Correct 603 ms 58808 KB Output is correct
9 Correct 51 ms 10136 KB Output is correct
10 Correct 592 ms 58716 KB Output is correct
11 Correct 280 ms 37080 KB Output is correct
12 Correct 607 ms 58940 KB Output is correct
13 Correct 283 ms 57880 KB Output is correct
14 Correct 304 ms 57528 KB Output is correct
15 Correct 270 ms 56672 KB Output is correct
16 Correct 280 ms 56692 KB Output is correct
17 Correct 298 ms 58036 KB Output is correct
18 Correct 275 ms 57016 KB Output is correct
19 Correct 285 ms 57280 KB Output is correct
20 Correct 340 ms 57288 KB Output is correct
21 Correct 264 ms 57672 KB Output is correct
22 Correct 274 ms 57436 KB Output is correct
23 Correct 276 ms 57428 KB Output is correct
24 Correct 276 ms 56724 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 15 ms 1092 KB Output is correct
9 Correct 3 ms 1156 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 7 ms 1100 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 2 ms 1096 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 2 ms 1100 KB Output is correct
16 Correct 2 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 14 ms 1092 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 15 ms 1100 KB Output is correct
21 Correct 2 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 2 ms 1100 KB Output is correct
24 Correct 2 ms 1100 KB Output is correct
25 Correct 137 ms 5760 KB Output is correct
26 Correct 17 ms 2124 KB Output is correct
27 Correct 216 ms 7784 KB Output is correct
28 Correct 248 ms 7784 KB Output is correct
29 Correct 115 ms 5840 KB Output is correct
30 Correct 136 ms 5776 KB Output is correct
31 Correct 154 ms 6040 KB Output is correct
32 Correct 250 ms 7764 KB Output is correct
33 Correct 191 ms 7492 KB Output is correct
34 Correct 85 ms 4684 KB Output is correct
35 Correct 184 ms 7984 KB Output is correct
36 Correct 217 ms 7752 KB Output is correct
37 Correct 107 ms 4568 KB Output is correct
38 Correct 461 ms 6848 KB Output is correct
39 Correct 27 ms 2372 KB Output is correct
40 Correct 282 ms 6852 KB Output is correct
41 Correct 152 ms 5584 KB Output is correct
42 Correct 214 ms 6800 KB Output is correct
43 Correct 62 ms 3320 KB Output is correct
44 Correct 188 ms 6780 KB Output is correct
45 Correct 37 ms 2548 KB Output is correct
46 Correct 186 ms 6732 KB Output is correct
47 Correct 48 ms 2860 KB Output is correct
48 Correct 246 ms 6748 KB Output is correct
49 Correct 569 ms 52876 KB Output is correct
50 Correct 634 ms 58824 KB Output is correct
51 Correct 343 ms 41600 KB Output is correct
52 Correct 551 ms 58800 KB Output is correct
53 Correct 192 ms 27528 KB Output is correct
54 Correct 541 ms 58808 KB Output is correct
55 Correct 443 ms 51032 KB Output is correct
56 Correct 603 ms 58808 KB Output is correct
57 Correct 51 ms 10136 KB Output is correct
58 Correct 592 ms 58716 KB Output is correct
59 Correct 280 ms 37080 KB Output is correct
60 Correct 607 ms 58940 KB Output is correct
61 Correct 283 ms 57880 KB Output is correct
62 Correct 304 ms 57528 KB Output is correct
63 Correct 270 ms 56672 KB Output is correct
64 Correct 280 ms 56692 KB Output is correct
65 Correct 298 ms 58036 KB Output is correct
66 Correct 275 ms 57016 KB Output is correct
67 Correct 285 ms 57280 KB Output is correct
68 Correct 340 ms 57288 KB Output is correct
69 Correct 264 ms 57672 KB Output is correct
70 Correct 274 ms 57436 KB Output is correct
71 Correct 276 ms 57428 KB Output is correct
72 Correct 276 ms 56724 KB Output is correct
73 Correct 865 ms 60712 KB Output is correct
74 Correct 603 ms 59700 KB Output is correct
75 Correct 763 ms 50948 KB Output is correct
76 Correct 1036 ms 68796 KB Output is correct
77 Correct 461 ms 34292 KB Output is correct
78 Correct 920 ms 65892 KB Output is correct
79 Correct 940 ms 61080 KB Output is correct
80 Correct 1109 ms 68936 KB Output is correct
81 Correct 319 ms 17216 KB Output is correct
82 Correct 727 ms 64088 KB Output is correct
83 Correct 733 ms 46412 KB Output is correct
84 Correct 1029 ms 68916 KB Output is correct
85 Correct 565 ms 63336 KB Output is correct
86 Correct 740 ms 66408 KB Output is correct
87 Correct 327 ms 58336 KB Output is correct
88 Correct 699 ms 65584 KB Output is correct
89 Correct 658 ms 64748 KB Output is correct
90 Correct 821 ms 66084 KB Output is correct
91 Correct 444 ms 60564 KB Output is correct
92 Correct 728 ms 66196 KB Output is correct
93 Correct 345 ms 59720 KB Output is correct
94 Correct 706 ms 66156 KB Output is correct
95 Correct 404 ms 60156 KB Output is correct
96 Correct 714 ms 65560 KB Output is correct