oj.uz

Submission #914643

# Submission time Handle Problem Language Result Execution time Memory
914643 2024-01-22T12:54:27 Z mychecksedad Fire (JOI20_ho_t5) C++17
14 / 100
 480 ms 163972 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 2e6+100, M = 1e5+10, K = 52, MX = 30;


int n, q, L[N], R[N];
ll a[N], ans[N], T[N], lazy[N], F[N], fazy[N];
vector<array<int, 3>> Q[N];
vector<array<ll, 3>> UPD[N];

void build(int l, int r, int k){
  if(l == r){
    F[k] = T[k] = lazy[k] = fazy[k] = 0;
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = F[k] = lazy[k] = fazy[k] = 0;
}

void push(int k, int l, int r, int m){
  T[k<<1] += lazy[k]*(ll)(m-l+1);
  T[k<<1|1] += lazy[k]*(ll)(r-m);
  lazy[k<<1] += lazy[k];
  lazy[k<<1|1] += lazy[k];
  lazy[k] = 0;
}
void push2(int k, int l, int r, int m){
  F[k<<1] += fazy[k]*(ll)(m-l+1);
  F[k<<1|1] += fazy[k]*(ll)(r-m);
  fazy[k<<1] += fazy[k];
  fazy[k<<1|1] += fazy[k];
  fazy[k] = 0;
}

void upd(int l, int r, int ql, int qr, int k, ll val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T[k] += (ll)(r-l+1)*val;
    lazy[k] += val;
    return;
  }
  int m = l+r>>1;
  push(k, l, r, m);
  upd(l, m, ql, qr, k<<1, val);
  upd(m+1, r, ql, qr, k<<1|1, val);
  T[k] = T[k<<1] + T[k<<1|1];
}
void upd2(int l, int r, int ql, int qr, int k, ll val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    F[k] += (ll)(r-l+1)*val;
    fazy[k] += val;
    return;
  }
  int m = l+r>>1;
  push2(k, l, r, m);
  upd2(l, m, ql, qr, k<<1, val);
  upd2(m+1, r, ql, qr, k<<1|1, val);
  F[k] = F[k<<1] + F[k<<1|1];
}

ll get(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return T[k];
  int m = l+r>>1;
  push(k, l, r, m);
  return get(l, m, ql, qr, k<<1) + get(m+1, r, ql, qr, k<<1|1);
}
ll get2(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return F[k];
  int m = l+r>>1;
  push2(k, l, r, m);
  return get2(l, m, ql, qr, k<<1) + get2(m+1, r, ql, qr, k<<1|1);
}

void add_triangle(int posd, int posv, ll val){
  if(posd >= 1 && posd <= 2*n) upd(1, 2*n, posd, 2*n, 1, val);
  if(posv < n) 
    upd2(1, n, posv + 1, n, 1, -val);
}

void solve(){
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  vector<int> qq;  
  qq.pb(n);
  L[n] = n + 1;
  for(int i = n-1; i >= 1; --i){
    while(!qq.empty() && a[qq.back()] < a[i]) qq.pop_back();
    if(qq.empty()) L[i] = n + 1;
    else L[i] = qq.back();
    qq.pb(i);
  }
  qq.clear();
  qq.pb(1);
  R[1] = 0;
  for(int i = 2; i <= n; ++i){
    while(!qq.empty() && a[qq.back()] < a[i]) qq.pop_back();
    if(qq.empty()) R[i] = 0;
    else R[i] = qq.back();
    qq.pb(i);
  }

  for(int i = 0; i < q; ++i){
    int t, l, r; cin >> t >> l >> r;
    Q[t].pb({l, r, i});
    ans[i] = 0;
    assert(t> 0);
  }
  build(1, 2*n, 1);

  for(int i = 1; i <= n; ++i){
    // cout << L[i] << ' ' << R[i] << '\n';
    if(R[i] > 0){
      int t = L[i]-1-i+i-R[i]-1, x = L[i] - 1;
      UPD[t].pb({n-t+x, x, a[i]}); 
      if(i-R[i]-2 >= 1)
        UPD[i-R[i]-2].pb({n-(i-R[i]-2)+i-1, i-1, -a[i]}); 
      if(L[i]-i-2 >= 1)
        UPD[L[i] - i - 2].pb({n-(L[i] - i - 2)+x, x, -a[i]}); 
    }else{
      upd2(1, n, i, L[i]-1, 1, a[i]);
      if(i < n && L[i]-i-2 >= 1)
        UPD[L[i]-i-2].pb({n-(L[i]-i-2)+L[i]-1, L[i]-1, -a[i]});
      // cout << i+n+1 << '\n';
    }
  }

  for(int i = n; i >= 1; --i){
    for(auto k: UPD[i]){
      add_triangle(k[0], k[1], k[2]);
      // cout << k[0] << ' ' << k[1] << ' ' << k[2] <<"triangle\n";
    }
    // cout << i << "\n";
    for(auto x: Q[i]){
      // cout << qq[0] << ' ' << qq[1] << ' ' << n-i+qq[0] << ' ' << n-i+qq[1] << '\n';
      ans[x[2]] = get(1, 2*n, n-i+x[0], n-i+x[1], 1) + get2(1, n, x[0], x[1], 1);
    }
  }


  for(int i = 0 ; i < q; ++i) cout << ans[i] << '\n';
}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

ho_t5.cpp: In function 'void build(int, int, int)':
ho_t5.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'void upd(int, int, int, int, int, long long int)':
ho_t5.cpp:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'void upd2(int, int, int, int, int, long long int)':
ho_t5.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'long long int get(int, int, int, int, int)':
ho_t5.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'long long int get2(int, int, int, int, int)':
ho_t5.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:159:15: warning: unused variable 'aa' [-Wunused-variable]
  159 |   int tt = 1, aa;
      |               ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 109144 KB Output is correct
2 Correct 31 ms 109404 KB Output is correct
3 Correct 31 ms 109400 KB Output is correct
4 Correct 32 ms 109384 KB Output is correct
5 Correct 32 ms 109400 KB Output is correct
6 Correct 34 ms 109268 KB Output is correct
7 Correct 34 ms 109268 KB Output is correct
8 Correct 32 ms 109404 KB Output is correct
9 Correct 34 ms 109400 KB Output is correct
10 Correct 33 ms 109400 KB Output is correct
11 Correct 32 ms 109136 KB Output is correct
12 Correct 32 ms 109404 KB Output is correct
13 Correct 32 ms 109396 KB Output is correct
14 Correct 33 ms 109404 KB Output is correct
15 Correct 33 ms 109404 KB Output is correct
16 Correct 31 ms 109288 KB Output is correct
17 Correct 32 ms 109136 KB Output is correct
18 Correct 32 ms 109284 KB Output is correct
19 Correct 32 ms 109148 KB Output is correct
20 Correct 34 ms 109400 KB Output is correct
21 Correct 34 ms 109256 KB Output is correct
22 Correct 32 ms 109404 KB Output is correct
23 Correct 31 ms 109376 KB Output is correct
24 Correct 32 ms 109404 KB Output is correct
25 Correct 33 ms 109404 KB Output is correct
26 Correct 32 ms 109400 KB Output is correct
27 Correct 32 ms 109404 KB Output is correct
28 Correct 33 ms 109260 KB Output is correct
29 Correct 31 ms 109392 KB Output is correct
30 Correct 32 ms 109140 KB Output is correct
31 Correct 31 ms 109252 KB Output is correct
32 Correct 32 ms 109252 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 109144 KB Output is correct
2 Correct 448 ms 159116 KB Output is correct
3 Correct 403 ms 158424 KB Output is correct
4 Correct 424 ms 159352 KB Output is correct
5 Correct 436 ms 163264 KB Output is correct
6 Correct 428 ms 159064 KB Output is correct
7 Correct 432 ms 158864 KB Output is correct
8 Correct 420 ms 163120 KB Output is correct
9 Correct 403 ms 161356 KB Output is correct
10 Correct 415 ms 158916 KB Output is correct
11 Correct 480 ms 161880 KB Output is correct
12 Correct 417 ms 158772 KB Output is correct
13 Correct 426 ms 162668 KB Output is correct
14 Correct 446 ms 163784 KB Output is correct
15 Correct 469 ms 163972 KB Output is correct
16 Correct 388 ms 158648 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 109144 KB Output is correct
2 Correct 447 ms 159280 KB Output is correct
3 Correct 397 ms 159180 KB Output is correct
4 Correct 449 ms 160276 KB Output is correct
5 Correct 417 ms 159208 KB Output is correct
6 Correct 384 ms 159600 KB Output is correct
7 Correct 462 ms 160688 KB Output is correct
8 Correct 419 ms 159512 KB Output is correct
9 Correct 442 ms 159244 KB Output is correct
10 Correct 425 ms 159132 KB Output is correct
11 Correct 438 ms 161212 KB Output is correct
12 Correct 413 ms 160216 KB Output is correct
13 Correct 442 ms 160336 KB Output is correct
14 Correct 423 ms 159260 KB Output is correct
15 Correct 410 ms 160452 KB Output is correct
16 Correct 412 ms 160608 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 446 ms 156420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 109144 KB Output is correct
2 Correct 31 ms 109404 KB Output is correct
3 Correct 31 ms 109400 KB Output is correct
4 Correct 32 ms 109384 KB Output is correct
5 Correct 32 ms 109400 KB Output is correct
6 Correct 34 ms 109268 KB Output is correct
7 Correct 34 ms 109268 KB Output is correct
8 Correct 32 ms 109404 KB Output is correct
9 Correct 34 ms 109400 KB Output is correct
10 Correct 33 ms 109400 KB Output is correct
11 Correct 32 ms 109136 KB Output is correct
12 Correct 32 ms 109404 KB Output is correct
13 Correct 32 ms 109396 KB Output is correct
14 Correct 33 ms 109404 KB Output is correct
15 Correct 33 ms 109404 KB Output is correct
16 Correct 31 ms 109288 KB Output is correct
17 Correct 32 ms 109136 KB Output is correct
18 Correct 32 ms 109284 KB Output is correct
19 Correct 32 ms 109148 KB Output is correct
20 Correct 34 ms 109400 KB Output is correct
21 Correct 34 ms 109256 KB Output is correct
22 Correct 32 ms 109404 KB Output is correct
23 Correct 31 ms 109376 KB Output is correct
24 Correct 32 ms 109404 KB Output is correct
25 Correct 33 ms 109404 KB Output is correct
26 Correct 32 ms 109400 KB Output is correct
27 Correct 32 ms 109404 KB Output is correct
28 Correct 33 ms 109260 KB Output is correct
29 Correct 31 ms 109392 KB Output is correct
30 Correct 32 ms 109140 KB Output is correct
31 Correct 31 ms 109252 KB Output is correct
32 Correct 32 ms 109252 KB Output is correct
33 Correct 448 ms 159116 KB Output is correct
34 Correct 403 ms 158424 KB Output is correct
35 Correct 424 ms 159352 KB Output is correct
36 Correct 436 ms 163264 KB Output is correct
37 Correct 428 ms 159064 KB Output is correct
38 Correct 432 ms 158864 KB Output is correct
39 Correct 420 ms 163120 KB Output is correct
40 Correct 403 ms 161356 KB Output is correct
41 Correct 415 ms 158916 KB Output is correct
42 Correct 480 ms 161880 KB Output is correct
43 Correct 417 ms 158772 KB Output is correct
44 Correct 426 ms 162668 KB Output is correct
45 Correct 446 ms 163784 KB Output is correct
46 Correct 469 ms 163972 KB Output is correct
47 Correct 388 ms 158648 KB Output is correct
48 Correct 447 ms 159280 KB Output is correct
49 Correct 397 ms 159180 KB Output is correct
50 Correct 449 ms 160276 KB Output is correct
51 Correct 417 ms 159208 KB Output is correct
52 Correct 384 ms 159600 KB Output is correct
53 Correct 462 ms 160688 KB Output is correct
54 Correct 419 ms 159512 KB Output is correct
55 Correct 442 ms 159244 KB Output is correct
56 Correct 425 ms 159132 KB Output is correct
57 Correct 438 ms 161212 KB Output is correct
58 Correct 413 ms 160216 KB Output is correct
59 Correct 442 ms 160336 KB Output is correct
60 Correct 423 ms 159260 KB Output is correct
61 Correct 410 ms 160452 KB Output is correct
62 Correct 412 ms 160608 KB Output is correct
63 Incorrect 446 ms 156420 KB Output isn't correct
64 Halted 0 ms 0 KB -