oj.uz

Submission #627689

# Submission time Handle Problem Language Result Execution time Memory
627689 2022-08-12T18:49:15 Z cadmiumsky Two Antennas (JOI19_antennas) C++17
100 / 100
 1038 ms 43716 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifdef DLOCAL
//  #define cin fin
//  #define cout fout
//  ifstream cin(".in");
//  ofstream cout(".out");
//#endif

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5, inf = 1e9 + 5;
int rez[nmax];

int n, q;

namespace AINT {
  int rez[nmax * 4], back[nmax * 4], front[nmax * 4];
  
  void init(int node = 1, int cl = 0, int cr = n - 1) {
    rez[node] = -1;
    back[node] = inf;
    front[node] = -1;
    if(cl != cr) {
      int mid = cl + cr >> 1;
      init(2 * node, cl, mid);
      init(2 * node + 1, mid + 1, cr);
    }
    return;
  }
  
  void push(int node, bool push) {
    rez[node] = max(rez[node], front[node] - back[node]);
    if(push)
      front[2 * node] = max(front[node], front[2 * node]),
      front[2 * node + 1] = max(front[node], front[2 * node + 1]),
      front[node] = -1;
  }
  
  int query(int l, int r, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(r < cl || cr < l)
      return -1;
    if(l <= cl && cr <= r) {
      //cerr << "Query: " << cl << ' ' << cr << ' ' << back[node] << ' ' << rez[node] << '\n';
      return rez[node];
    }
    int mid = cl + cr >> 1;
    return max(query(l, r, 2 * node ,cl, mid), query(l, r, 2 * node + 1, mid + 1, cr));
  }
  
  void updback(int poz, int val, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(poz < cl || cr < poz)
      return;
    if(cl == cr) {
      front[node] = -1;
      back[node] = val;
      return;
    }
    int mid = cl + cr >> 1;
    updback(poz, val, 2 * node, cl, mid);
    updback(poz, val, 2 * node + 1, mid + 1, cr);
    back[node] = min(back[2 * node], back[2 * node + 1]);
    //cerr << cl << ' ' << cr << ' ' << back[node] << ' ' << rez[node] << '\n';
  }
  
  void updfront(int l, int r, int val, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(r < cl || cr < l)
      return;
    
    if(l <= cl && cr <= r) {
      front[node] = val;
      //cerr << "AddFront: " << cl << ' ' << cr << ' ' << val << ' ' << back[node] << '\n';
      push(node, cl != cr);
      //cerr << "AddFront: " << cl << ' ' << cr << ' ' << val << ' ' << back[node] << ' ' << rez[node] << '\n';
      return;
    }
    
    int mid = cl + cr >> 1;
    updfront(l, r, val, 2 * node, cl, mid);
    updfront(l, r, val, 2 * node + 1, mid + 1, cr);
    rez[node] = max(rez[2 * node], rez[2 * node + 1]);
    //cerr << cl << ' ' << cr << ' ' << rez[node] << '\n';
  }
}

vector<pii> qsevents[nmax];
vector<int> antevents[nmax]; 
void solve(vector<tii> ant, vector<pii> qs) {
  AINT::init(); 
  for(int i = 0; i < n; i++) {
    qsevents[i].clear();
    antevents[i].clear();
  }
  
  //for(auto [l, r] : qs)
    //cout << l << ' ' << r << '\n';
  
  for(int A, B, H, i = 0; i < n; i++) {
    tie(A, B, H) = ant[i];
    
    if(i - A >= 0)	
      antevents[i - A].emplace_back(i);
    if(i - B > 0)	
      antevents[i - B - 1].emplace_back(-i - 1);
  }
  int ind = 0;
  for(auto [l, r] : qs)
    qsevents[l].emplace_back(r, ind),
    ind++;
  
  for(int A, B, H, i = n - 1; i >= 0; i--) {
    tie(A, B, H) = ant[i];
    
    for(auto x : antevents[i]) {
      if(x >= 0)
	//cerr << "+ " << x << ' ' << get<2>(ant[x]) << '\n',
	AINT::updback(x, get<2>(ant[x]));
      else {
	//cerr << "+ " << x + 1 << '\n';
	x = -(x + 1);
	AINT::updback(x, inf);
      } 
    }
    
    //cerr << H << ' ' << i + A << ' ' << i + B << '\n';
    AINT::updfront(i + A, i + B, H);
  
    for(auto [r, idx] : qsevents[i]) {
      rez[idx] = max(rez[idx], AINT::query(i, r));
    }
  }
  
  return;
}

signed main() {
  vector<tii> ant;
  vector<pii> qs;
  cin >> n;
  ant.resize(n);
  for(auto &[a, b, h] : ant)
    cin >> h >> a >> b;
  
  cin >> q;
  for(int i = 0; i < q; i++) rez[i] = -1;
  qs.resize(q);
  for(auto &[l, r] : qs)
    cin >> l >> r,
    --l,
    --r;
  
  solve(ant, qs);
  
  reverse(ant.begin(), ant.end());
  for(auto &[l, r] : qs)
    l = n - l - 1,
    r = n - r - 1,
    swap(l, r);
  solve(ant, qs);
  
  for(int i = 0; i < q; i++)
    cout << rez[i] << '\n';
  return 0;
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message

antennas.cpp: In function 'void AINT::init(int, int, int)':
antennas.cpp:32:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
antennas.cpp: In function 'int AINT::query(int, int, int, int, int)':
antennas.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
antennas.cpp: In function 'void AINT::updback(int, int, int, int, int)':
antennas.cpp:68:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
antennas.cpp: In function 'void AINT::updfront(int, int, int, int, int, int)':
antennas.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 7 ms 9704 KB Output is correct
10 Correct 7 ms 9716 KB Output is correct
11 Correct 6 ms 9624 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9736 KB Output is correct
14 Correct 7 ms 9708 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 6 ms 9764 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9716 KB Output is correct
20 Correct 6 ms 9740 KB Output is correct
21 Correct 6 ms 9708 KB Output is correct
22 Correct 7 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 7 ms 9704 KB Output is correct
10 Correct 7 ms 9716 KB Output is correct
11 Correct 6 ms 9624 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9736 KB Output is correct
14 Correct 7 ms 9708 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 6 ms 9764 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9716 KB Output is correct
20 Correct 6 ms 9740 KB Output is correct
21 Correct 6 ms 9708 KB Output is correct
22 Correct 7 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 160 ms 17824 KB Output is correct
26 Correct 28 ms 10712 KB Output is correct
27 Correct 237 ms 20856 KB Output is correct
28 Correct 267 ms 20792 KB Output is correct
29 Correct 166 ms 17904 KB Output is correct
30 Correct 162 ms 17288 KB Output is correct
31 Correct 191 ms 19956 KB Output is correct
32 Correct 220 ms 20740 KB Output is correct
33 Correct 218 ms 20532 KB Output is correct
34 Correct 120 ms 15136 KB Output is correct
35 Correct 226 ms 21100 KB Output is correct
36 Correct 273 ms 20864 KB Output is correct
37 Correct 146 ms 15580 KB Output is correct
38 Correct 241 ms 19776 KB Output is correct
39 Correct 40 ms 11252 KB Output is correct
40 Correct 330 ms 19820 KB Output is correct
41 Correct 195 ms 17496 KB Output is correct
42 Correct 260 ms 19716 KB Output is correct
43 Correct 80 ms 13128 KB Output is correct
44 Correct 251 ms 19760 KB Output is correct
45 Correct 72 ms 11488 KB Output is correct
46 Correct 238 ms 19828 KB Output is correct
47 Correct 69 ms 12372 KB Output is correct
48 Correct 252 ms 19816 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 27748 KB Output is correct
2 Correct 471 ms 29120 KB Output is correct
3 Correct 370 ms 25120 KB Output is correct
4 Correct 488 ms 29144 KB Output is correct
5 Correct 221 ms 18736 KB Output is correct
6 Correct 487 ms 29140 KB Output is correct
7 Correct 497 ms 27356 KB Output is correct
8 Correct 535 ms 29144 KB Output is correct
9 Correct 73 ms 12504 KB Output is correct
10 Correct 658 ms 29144 KB Output is correct
11 Correct 326 ms 21028 KB Output is correct
12 Correct 586 ms 29156 KB Output is correct
13 Correct 402 ms 28356 KB Output is correct
14 Correct 386 ms 27824 KB Output is correct
15 Correct 396 ms 26976 KB Output is correct
16 Correct 393 ms 27100 KB Output is correct
17 Correct 429 ms 28672 KB Output is correct
18 Correct 417 ms 27556 KB Output is correct
19 Correct 413 ms 27728 KB Output is correct
20 Correct 379 ms 27920 KB Output is correct
21 Correct 365 ms 28232 KB Output is correct
22 Correct 378 ms 27840 KB Output is correct
23 Correct 380 ms 27816 KB Output is correct
24 Correct 368 ms 26860 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9696 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 7 ms 9704 KB Output is correct
10 Correct 7 ms 9716 KB Output is correct
11 Correct 6 ms 9624 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9736 KB Output is correct
14 Correct 7 ms 9708 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 6 ms 9764 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9716 KB Output is correct
20 Correct 6 ms 9740 KB Output is correct
21 Correct 6 ms 9708 KB Output is correct
22 Correct 7 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 160 ms 17824 KB Output is correct
26 Correct 28 ms 10712 KB Output is correct
27 Correct 237 ms 20856 KB Output is correct
28 Correct 267 ms 20792 KB Output is correct
29 Correct 166 ms 17904 KB Output is correct
30 Correct 162 ms 17288 KB Output is correct
31 Correct 191 ms 19956 KB Output is correct
32 Correct 220 ms 20740 KB Output is correct
33 Correct 218 ms 20532 KB Output is correct
34 Correct 120 ms 15136 KB Output is correct
35 Correct 226 ms 21100 KB Output is correct
36 Correct 273 ms 20864 KB Output is correct
37 Correct 146 ms 15580 KB Output is correct
38 Correct 241 ms 19776 KB Output is correct
39 Correct 40 ms 11252 KB Output is correct
40 Correct 330 ms 19820 KB Output is correct
41 Correct 195 ms 17496 KB Output is correct
42 Correct 260 ms 19716 KB Output is correct
43 Correct 80 ms 13128 KB Output is correct
44 Correct 251 ms 19760 KB Output is correct
45 Correct 72 ms 11488 KB Output is correct
46 Correct 238 ms 19828 KB Output is correct
47 Correct 69 ms 12372 KB Output is correct
48 Correct 252 ms 19816 KB Output is correct
49 Correct 499 ms 27748 KB Output is correct
50 Correct 471 ms 29120 KB Output is correct
51 Correct 370 ms 25120 KB Output is correct
52 Correct 488 ms 29144 KB Output is correct
53 Correct 221 ms 18736 KB Output is correct
54 Correct 487 ms 29140 KB Output is correct
55 Correct 497 ms 27356 KB Output is correct
56 Correct 535 ms 29144 KB Output is correct
57 Correct 73 ms 12504 KB Output is correct
58 Correct 658 ms 29144 KB Output is correct
59 Correct 326 ms 21028 KB Output is correct
60 Correct 586 ms 29156 KB Output is correct
61 Correct 402 ms 28356 KB Output is correct
62 Correct 386 ms 27824 KB Output is correct
63 Correct 396 ms 26976 KB Output is correct
64 Correct 393 ms 27100 KB Output is correct
65 Correct 429 ms 28672 KB Output is correct
66 Correct 417 ms 27556 KB Output is correct
67 Correct 413 ms 27728 KB Output is correct
68 Correct 379 ms 27920 KB Output is correct
69 Correct 365 ms 28232 KB Output is correct
70 Correct 378 ms 27840 KB Output is correct
71 Correct 380 ms 27816 KB Output is correct
72 Correct 368 ms 26860 KB Output is correct
73 Correct 759 ms 38924 KB Output is correct
74 Correct 498 ms 30652 KB Output is correct
75 Correct 728 ms 39088 KB Output is correct
76 Correct 893 ms 43716 KB Output is correct
77 Correct 475 ms 28732 KB Output is correct
78 Correct 836 ms 39476 KB Output is correct
79 Correct 975 ms 41648 KB Output is correct
80 Correct 1038 ms 43672 KB Output is correct
81 Correct 420 ms 24272 KB Output is correct
82 Correct 688 ms 37108 KB Output is correct
83 Correct 659 ms 34536 KB Output is correct
84 Correct 949 ms 43708 KB Output is correct
85 Correct 694 ms 36632 KB Output is correct
86 Correct 789 ms 41172 KB Output is correct
87 Correct 450 ms 29512 KB Output is correct
88 Correct 802 ms 40460 KB Output is correct
89 Correct 744 ms 38884 KB Output is correct
90 Correct 805 ms 40948 KB Output is correct
91 Correct 532 ms 32888 KB Output is correct
92 Correct 806 ms 41088 KB Output is correct
93 Correct 452 ms 30872 KB Output is correct
94 Correct 810 ms 41204 KB Output is correct
95 Correct 494 ms 32076 KB Output is correct
96 Correct 817 ms 40140 KB Output is correct