oj.uz

Submission #926318

# Submission time Handle Problem Language Result Execution time Memory
926318 2024-02-12T19:21:34 Z AdamGS Fire (JOI20_ho_t5) C++17
100 / 100
 543 ms 88132 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct pas {
  ll x1, y1, x2, y2, d;
};
const int LIM=2e5+7;
ll T[LIM], dlu[LIM], kon[LIM], wynik[LIM], tr[4*LIM], lazy[4*LIM], N=1;
vector<pair<ll,ll>>V;
vector<pas>dod, pyt;
void spl(int v) {
  tr[2*v]+=lazy[v]/2;
  tr[2*v+1]+=lazy[v]/2;
  lazy[2*v]+=lazy[v]/2;
  lazy[2*v+1]+=lazy[v]/2;
  lazy[v]=0;
}
void upd(int v, ll l, ll r, int a, int b, ll x) {
  if(b<l || r<a) return;
  if(a<=l && r<=b) {
    tr[v]+=(r-l+1)*x;
    lazy[v]+=(r-l+1)*x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=tr[2*v]+tr[2*v+1];
}
ll cnt(int v, int l, int r, int a, int b) {
  if(b<l || r<a) return 0;
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return cnt(2*v, l, mid, a, b)+cnt(2*v+1, mid+1, r, a, b);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  while(N<n) N*=2;
  rep(i, n) cin >> T[i];
  vector<int>P;
  for(int i=n-1; i>=0; --i) {
    while(P.size() && T[P.back()]<T[i]) {
      dod.pb({P.back(), P.back()-i, P.back()+dlu[P.back()]-1, P.back()-i+dlu[P.back()]-1, -T[P.back()]});
      V.pb({-i, -(int)dod.size()});
      P.pop_back();
    }
    if(P.size()) dlu[i]=P.back()-i; else dlu[i]=n-i;
    dod.pb({i, 0, i+dlu[i]-1, dlu[i]-1, T[i]});
    V.pb({-i, -(int)dod.size()});
    P.pb(i);
  }
  rep(i, q) {
    ll t, l, r;
    cin >> t >> l >> r; --l; --r;
    pyt.pb({r, t, i, 1, 0});
    V.pb({t-r, pyt.size()});
    if(l!=0) {
      pyt.pb({l-1, t, i, -1, 0});
      V.pb({t-l+1, pyt.size()});
    }
  }
  sort(all(V));
  for(auto i : V) {
    int p=abs(i.nd)-1;
    if(i.nd<0) upd(1, 0, N-1, dod[p].x1, dod[p].x2, dod[p].d);
    else wynik[pyt[p].x2]+=cnt(1, 0, N-1, 0, pyt[p].x1)*pyt[p].y2;
  }
  rep(i, 2*N) tr[i]=lazy[i]=0;
  reverse(all(V));
  for(auto i : V) {
    int p=abs(i.nd)-1;
    if(i.nd<0) upd(1, 0, N-1, dod[p].y1, dod[p].y2, dod[p].d);
    else wynik[pyt[p].x2]+=cnt(1, 0, N-1, 0, pyt[p].y1)*pyt[p].y2;
  }
  rep(i, q) cout << wynik[i] << '\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8792 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 8796 KB Output is correct
31 Correct 2 ms 8536 KB Output is correct
32 Correct 2 ms 8540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 419 ms 86288 KB Output is correct
3 Correct 401 ms 87360 KB Output is correct
4 Correct 467 ms 87368 KB Output is correct
5 Correct 396 ms 72796 KB Output is correct
6 Correct 448 ms 86728 KB Output is correct
7 Correct 439 ms 86060 KB Output is correct
8 Correct 433 ms 71692 KB Output is correct
9 Correct 434 ms 87772 KB Output is correct
10 Correct 421 ms 85596 KB Output is correct
11 Correct 432 ms 72860 KB Output is correct
12 Correct 407 ms 85996 KB Output is correct
13 Correct 412 ms 72012 KB Output is correct
14 Correct 442 ms 72192 KB Output is correct
15 Correct 405 ms 70552 KB Output is correct
16 Correct 458 ms 86924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 489 ms 85368 KB Output is correct
3 Correct 445 ms 85828 KB Output is correct
4 Correct 452 ms 71476 KB Output is correct
5 Correct 443 ms 85636 KB Output is correct
6 Correct 447 ms 85896 KB Output is correct
7 Correct 436 ms 69656 KB Output is correct
8 Correct 516 ms 84664 KB Output is correct
9 Correct 457 ms 85396 KB Output is correct
10 Correct 461 ms 85252 KB Output is correct
11 Correct 443 ms 69848 KB Output is correct
12 Correct 449 ms 70436 KB Output is correct
13 Correct 464 ms 71156 KB Output is correct
14 Correct 439 ms 85260 KB Output is correct
15 Correct 450 ms 69944 KB Output is correct
16 Correct 450 ms 70572 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 77668 KB Output is correct
2 Correct 441 ms 77512 KB Output is correct
3 Correct 447 ms 79156 KB Output is correct
4 Correct 464 ms 77380 KB Output is correct
5 Correct 434 ms 78628 KB Output is correct
6 Correct 425 ms 77920 KB Output is correct
7 Correct 444 ms 78024 KB Output is correct
8 Correct 448 ms 78532 KB Output is correct
9 Correct 425 ms 77516 KB Output is correct
10 Correct 427 ms 79296 KB Output is correct
11 Correct 428 ms 77696 KB Output is correct
12 Correct 426 ms 77048 KB Output is correct
13 Correct 467 ms 78768 KB Output is correct
14 Correct 438 ms 77576 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8792 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 8796 KB Output is correct
31 Correct 2 ms 8536 KB Output is correct
32 Correct 2 ms 8540 KB Output is correct
33 Correct 419 ms 86288 KB Output is correct
34 Correct 401 ms 87360 KB Output is correct
35 Correct 467 ms 87368 KB Output is correct
36 Correct 396 ms 72796 KB Output is correct
37 Correct 448 ms 86728 KB Output is correct
38 Correct 439 ms 86060 KB Output is correct
39 Correct 433 ms 71692 KB Output is correct
40 Correct 434 ms 87772 KB Output is correct
41 Correct 421 ms 85596 KB Output is correct
42 Correct 432 ms 72860 KB Output is correct
43 Correct 407 ms 85996 KB Output is correct
44 Correct 412 ms 72012 KB Output is correct
45 Correct 442 ms 72192 KB Output is correct
46 Correct 405 ms 70552 KB Output is correct
47 Correct 458 ms 86924 KB Output is correct
48 Correct 489 ms 85368 KB Output is correct
49 Correct 445 ms 85828 KB Output is correct
50 Correct 452 ms 71476 KB Output is correct
51 Correct 443 ms 85636 KB Output is correct
52 Correct 447 ms 85896 KB Output is correct
53 Correct 436 ms 69656 KB Output is correct
54 Correct 516 ms 84664 KB Output is correct
55 Correct 457 ms 85396 KB Output is correct
56 Correct 461 ms 85252 KB Output is correct
57 Correct 443 ms 69848 KB Output is correct
58 Correct 449 ms 70436 KB Output is correct
59 Correct 464 ms 71156 KB Output is correct
60 Correct 439 ms 85260 KB Output is correct
61 Correct 450 ms 69944 KB Output is correct
62 Correct 450 ms 70572 KB Output is correct
63 Correct 449 ms 77668 KB Output is correct
64 Correct 441 ms 77512 KB Output is correct
65 Correct 447 ms 79156 KB Output is correct
66 Correct 464 ms 77380 KB Output is correct
67 Correct 434 ms 78628 KB Output is correct
68 Correct 425 ms 77920 KB Output is correct
69 Correct 444 ms 78024 KB Output is correct
70 Correct 448 ms 78532 KB Output is correct
71 Correct 425 ms 77516 KB Output is correct
72 Correct 427 ms 79296 KB Output is correct
73 Correct 428 ms 77696 KB Output is correct
74 Correct 426 ms 77048 KB Output is correct
75 Correct 467 ms 78768 KB Output is correct
76 Correct 438 ms 77576 KB Output is correct
77 Correct 528 ms 86724 KB Output is correct
78 Correct 519 ms 86276 KB Output is correct
79 Correct 496 ms 71048 KB Output is correct
80 Correct 484 ms 85716 KB Output is correct
81 Correct 538 ms 86876 KB Output is correct
82 Correct 543 ms 86216 KB Output is correct
83 Correct 495 ms 87312 KB Output is correct
84 Correct 512 ms 85956 KB Output is correct
85 Correct 534 ms 70976 KB Output is correct
86 Correct 530 ms 85864 KB Output is correct
87 Correct 459 ms 73896 KB Output is correct
88 Correct 451 ms 71848 KB Output is correct
89 Correct 469 ms 86844 KB Output is correct
90 Correct 455 ms 72828 KB Output is correct
91 Correct 418 ms 87200 KB Output is correct
92 Correct 416 ms 85440 KB Output is correct
93 Correct 448 ms 85700 KB Output is correct
94 Correct 453 ms 71744 KB Output is correct
95 Correct 446 ms 71380 KB Output is correct
96 Correct 426 ms 88132 KB Output is correct
97 Correct 465 ms 87748 KB Output is correct
98 Correct 463 ms 86872 KB Output is correct
99 Correct 459 ms 85712 KB Output is correct
100 Correct 457 ms 85936 KB Output is correct
101 Correct 469 ms 86044 KB Output is correct
102 Correct 481 ms 71972 KB Output is correct