oj.uz

Submission #914633

# Submission time Handle Problem Language Result Execution time Memory
914633 2024-01-22T12:32:33 Z mychecksedad Fire (JOI20_ho_t5) C++17
14 / 100
 448 ms 169152 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){
  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;
  }
  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:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'void upd(int, int, int, int, int, long long int)':
ho_t5.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'void upd2(int, int, int, int, int, long long int)':
ho_t5.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'long long int get(int, int, int, int, int)':
ho_t5.cpp:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int m = l+r>>1;
      |           ~^~
ho_t5.cpp: In function 'long long int get2(int, int, int, int, int)':
ho_t5.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   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 32 ms 109148 KB Output is correct
2 Correct 32 ms 109404 KB Output is correct
3 Correct 32 ms 109404 KB Output is correct
4 Correct 32 ms 109396 KB Output is correct
5 Correct 32 ms 109400 KB Output is correct
6 Correct 32 ms 109404 KB Output is correct
7 Correct 34 ms 109404 KB Output is correct
8 Correct 31 ms 109404 KB Output is correct
9 Correct 31 ms 109404 KB Output is correct
10 Correct 34 ms 109256 KB Output is correct
11 Correct 32 ms 109276 KB Output is correct
12 Correct 31 ms 109404 KB Output is correct
13 Correct 31 ms 109364 KB Output is correct
14 Correct 33 ms 109404 KB Output is correct
15 Correct 32 ms 109312 KB Output is correct
16 Correct 32 ms 109400 KB Output is correct
17 Correct 32 ms 109404 KB Output is correct
18 Correct 32 ms 109396 KB Output is correct
19 Correct 31 ms 109400 KB Output is correct
20 Correct 32 ms 109404 KB Output is correct
21 Correct 33 ms 109288 KB Output is correct
22 Correct 31 ms 109400 KB Output is correct
23 Correct 31 ms 109404 KB Output is correct
24 Correct 31 ms 109404 KB Output is correct
25 Correct 32 ms 109400 KB Output is correct
26 Correct 32 ms 109404 KB Output is correct
27 Correct 31 ms 109252 KB Output is correct
28 Correct 33 ms 109400 KB Output is correct
29 Correct 32 ms 109316 KB Output is correct
30 Correct 32 ms 109288 KB Output is correct
31 Correct 31 ms 109400 KB Output is correct
32 Correct 32 ms 109404 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 109148 KB Output is correct
2 Correct 387 ms 158868 KB Output is correct
3 Correct 407 ms 164436 KB Output is correct
4 Correct 431 ms 164548 KB Output is correct
5 Correct 398 ms 168064 KB Output is correct
6 Correct 396 ms 164580 KB Output is correct
7 Correct 425 ms 164464 KB Output is correct
8 Correct 409 ms 169152 KB Output is correct
9 Correct 399 ms 166128 KB Output is correct
10 Correct 433 ms 165224 KB Output is correct
11 Correct 429 ms 167316 KB Output is correct
12 Correct 398 ms 164868 KB Output is correct
13 Correct 429 ms 168128 KB Output is correct
14 Correct 448 ms 168568 KB Output is correct
15 Correct 427 ms 168044 KB Output is correct
16 Correct 404 ms 164352 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 109148 KB Output is correct
2 Correct 434 ms 159688 KB Output is correct
3 Correct 421 ms 164696 KB Output is correct
4 Correct 394 ms 166500 KB Output is correct
5 Correct 379 ms 164712 KB Output is correct
6 Correct 386 ms 165048 KB Output is correct
7 Correct 422 ms 165620 KB Output is correct
8 Correct 399 ms 164972 KB Output is correct
9 Correct 440 ms 164824 KB Output is correct
10 Correct 411 ms 164720 KB Output is correct
11 Correct 403 ms 166096 KB Output is correct
12 Correct 407 ms 165672 KB Output is correct
13 Correct 432 ms 166496 KB Output is correct
14 Correct 404 ms 164972 KB Output is correct
15 Correct 428 ms 165744 KB Output is correct
16 Correct 393 ms 165936 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 109148 KB Output is correct
2 Correct 32 ms 109404 KB Output is correct
3 Correct 32 ms 109404 KB Output is correct
4 Correct 32 ms 109396 KB Output is correct
5 Correct 32 ms 109400 KB Output is correct
6 Correct 32 ms 109404 KB Output is correct
7 Correct 34 ms 109404 KB Output is correct
8 Correct 31 ms 109404 KB Output is correct
9 Correct 31 ms 109404 KB Output is correct
10 Correct 34 ms 109256 KB Output is correct
11 Correct 32 ms 109276 KB Output is correct
12 Correct 31 ms 109404 KB Output is correct
13 Correct 31 ms 109364 KB Output is correct
14 Correct 33 ms 109404 KB Output is correct
15 Correct 32 ms 109312 KB Output is correct
16 Correct 32 ms 109400 KB Output is correct
17 Correct 32 ms 109404 KB Output is correct
18 Correct 32 ms 109396 KB Output is correct
19 Correct 31 ms 109400 KB Output is correct
20 Correct 32 ms 109404 KB Output is correct
21 Correct 33 ms 109288 KB Output is correct
22 Correct 31 ms 109400 KB Output is correct
23 Correct 31 ms 109404 KB Output is correct
24 Correct 31 ms 109404 KB Output is correct
25 Correct 32 ms 109400 KB Output is correct
26 Correct 32 ms 109404 KB Output is correct
27 Correct 31 ms 109252 KB Output is correct
28 Correct 33 ms 109400 KB Output is correct
29 Correct 32 ms 109316 KB Output is correct
30 Correct 32 ms 109288 KB Output is correct
31 Correct 31 ms 109400 KB Output is correct
32 Correct 32 ms 109404 KB Output is correct
33 Correct 387 ms 158868 KB Output is correct
34 Correct 407 ms 164436 KB Output is correct
35 Correct 431 ms 164548 KB Output is correct
36 Correct 398 ms 168064 KB Output is correct
37 Correct 396 ms 164580 KB Output is correct
38 Correct 425 ms 164464 KB Output is correct
39 Correct 409 ms 169152 KB Output is correct
40 Correct 399 ms 166128 KB Output is correct
41 Correct 433 ms 165224 KB Output is correct
42 Correct 429 ms 167316 KB Output is correct
43 Correct 398 ms 164868 KB Output is correct
44 Correct 429 ms 168128 KB Output is correct
45 Correct 448 ms 168568 KB Output is correct
46 Correct 427 ms 168044 KB Output is correct
47 Correct 404 ms 164352 KB Output is correct
48 Correct 434 ms 159688 KB Output is correct
49 Correct 421 ms 164696 KB Output is correct
50 Correct 394 ms 166500 KB Output is correct
51 Correct 379 ms 164712 KB Output is correct
52 Correct 386 ms 165048 KB Output is correct
53 Correct 422 ms 165620 KB Output is correct
54 Correct 399 ms 164972 KB Output is correct
55 Correct 440 ms 164824 KB Output is correct
56 Correct 411 ms 164720 KB Output is correct
57 Correct 403 ms 166096 KB Output is correct
58 Correct 407 ms 165672 KB Output is correct
59 Correct 432 ms 166496 KB Output is correct
60 Correct 404 ms 164972 KB Output is correct
61 Correct 428 ms 165744 KB Output is correct
62 Correct 393 ms 165936 KB Output is correct
63 Incorrect 394 ms 156488 KB Output isn't correct
64 Halted 0 ms 0 KB -