oj.uz

Submission #914644

# Submission time Handle Problem Language Result Execution time Memory
914644 2024-01-22T12:57:18 Z mychecksedad Fire (JOI20_ho_t5) C++17
14 / 100
 495 ms 214724 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 = 3e6+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 45 ms 156496 KB Output is correct
2 Correct 45 ms 156500 KB Output is correct
3 Correct 45 ms 156504 KB Output is correct
4 Correct 47 ms 156500 KB Output is correct
5 Correct 46 ms 156496 KB Output is correct
6 Correct 48 ms 156504 KB Output is correct
7 Correct 47 ms 156452 KB Output is correct
8 Correct 47 ms 156508 KB Output is correct
9 Correct 45 ms 156496 KB Output is correct
10 Correct 47 ms 156496 KB Output is correct
11 Correct 46 ms 156500 KB Output is correct
12 Correct 48 ms 156500 KB Output is correct
13 Correct 45 ms 156504 KB Output is correct
14 Correct 45 ms 156508 KB Output is correct
15 Correct 45 ms 156496 KB Output is correct
16 Correct 46 ms 156512 KB Output is correct
17 Correct 49 ms 156508 KB Output is correct
18 Correct 46 ms 156504 KB Output is correct
19 Correct 47 ms 156504 KB Output is correct
20 Correct 48 ms 156508 KB Output is correct
21 Correct 46 ms 156500 KB Output is correct
22 Correct 45 ms 156496 KB Output is correct
23 Correct 46 ms 156364 KB Output is correct
24 Correct 46 ms 156504 KB Output is correct
25 Correct 46 ms 156508 KB Output is correct
26 Correct 46 ms 156500 KB Output is correct
27 Correct 48 ms 156508 KB Output is correct
28 Correct 45 ms 156500 KB Output is correct
29 Correct 47 ms 156508 KB Output is correct
30 Correct 46 ms 156564 KB Output is correct
31 Correct 46 ms 156508 KB Output is correct
32 Correct 45 ms 156496 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 156496 KB Output is correct
2 Correct 439 ms 210108 KB Output is correct
3 Correct 443 ms 210020 KB Output is correct
4 Correct 427 ms 210388 KB Output is correct
5 Correct 463 ms 213720 KB Output is correct
6 Correct 423 ms 210584 KB Output is correct
7 Correct 421 ms 210252 KB Output is correct
8 Correct 436 ms 214080 KB Output is correct
9 Correct 452 ms 212836 KB Output is correct
10 Correct 414 ms 210620 KB Output is correct
11 Correct 470 ms 212408 KB Output is correct
12 Correct 433 ms 210228 KB Output is correct
13 Correct 414 ms 214468 KB Output is correct
14 Correct 466 ms 214708 KB Output is correct
15 Correct 435 ms 214724 KB Output is correct
16 Correct 408 ms 210680 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 156496 KB Output is correct
2 Correct 495 ms 210576 KB Output is correct
3 Correct 429 ms 210436 KB Output is correct
4 Correct 430 ms 211420 KB Output is correct
5 Correct 432 ms 210516 KB Output is correct
6 Correct 447 ms 210672 KB Output is correct
7 Correct 421 ms 212048 KB Output is correct
8 Correct 424 ms 210628 KB Output is correct
9 Correct 431 ms 210536 KB Output is correct
10 Correct 472 ms 210588 KB Output is correct
11 Correct 428 ms 212068 KB Output is correct
12 Correct 448 ms 212064 KB Output is correct
13 Correct 437 ms 212384 KB Output is correct
14 Correct 399 ms 210580 KB Output is correct
15 Correct 474 ms 211336 KB Output is correct
16 Correct 433 ms 211348 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 156496 KB Output is correct
2 Correct 45 ms 156500 KB Output is correct
3 Correct 45 ms 156504 KB Output is correct
4 Correct 47 ms 156500 KB Output is correct
5 Correct 46 ms 156496 KB Output is correct
6 Correct 48 ms 156504 KB Output is correct
7 Correct 47 ms 156452 KB Output is correct
8 Correct 47 ms 156508 KB Output is correct
9 Correct 45 ms 156496 KB Output is correct
10 Correct 47 ms 156496 KB Output is correct
11 Correct 46 ms 156500 KB Output is correct
12 Correct 48 ms 156500 KB Output is correct
13 Correct 45 ms 156504 KB Output is correct
14 Correct 45 ms 156508 KB Output is correct
15 Correct 45 ms 156496 KB Output is correct
16 Correct 46 ms 156512 KB Output is correct
17 Correct 49 ms 156508 KB Output is correct
18 Correct 46 ms 156504 KB Output is correct
19 Correct 47 ms 156504 KB Output is correct
20 Correct 48 ms 156508 KB Output is correct
21 Correct 46 ms 156500 KB Output is correct
22 Correct 45 ms 156496 KB Output is correct
23 Correct 46 ms 156364 KB Output is correct
24 Correct 46 ms 156504 KB Output is correct
25 Correct 46 ms 156508 KB Output is correct
26 Correct 46 ms 156500 KB Output is correct
27 Correct 48 ms 156508 KB Output is correct
28 Correct 45 ms 156500 KB Output is correct
29 Correct 47 ms 156508 KB Output is correct
30 Correct 46 ms 156564 KB Output is correct
31 Correct 46 ms 156508 KB Output is correct
32 Correct 45 ms 156496 KB Output is correct
33 Correct 439 ms 210108 KB Output is correct
34 Correct 443 ms 210020 KB Output is correct
35 Correct 427 ms 210388 KB Output is correct
36 Correct 463 ms 213720 KB Output is correct
37 Correct 423 ms 210584 KB Output is correct
38 Correct 421 ms 210252 KB Output is correct
39 Correct 436 ms 214080 KB Output is correct
40 Correct 452 ms 212836 KB Output is correct
41 Correct 414 ms 210620 KB Output is correct
42 Correct 470 ms 212408 KB Output is correct
43 Correct 433 ms 210228 KB Output is correct
44 Correct 414 ms 214468 KB Output is correct
45 Correct 466 ms 214708 KB Output is correct
46 Correct 435 ms 214724 KB Output is correct
47 Correct 408 ms 210680 KB Output is correct
48 Correct 495 ms 210576 KB Output is correct
49 Correct 429 ms 210436 KB Output is correct
50 Correct 430 ms 211420 KB Output is correct
51 Correct 432 ms 210516 KB Output is correct
52 Correct 447 ms 210672 KB Output is correct
53 Correct 421 ms 212048 KB Output is correct
54 Correct 424 ms 210628 KB Output is correct
55 Correct 431 ms 210536 KB Output is correct
56 Correct 472 ms 210588 KB Output is correct
57 Correct 428 ms 212068 KB Output is correct
58 Correct 448 ms 212064 KB Output is correct
59 Correct 437 ms 212384 KB Output is correct
60 Correct 399 ms 210580 KB Output is correct
61 Correct 474 ms 211336 KB Output is correct
62 Correct 433 ms 211348 KB Output is correct
63 Incorrect 434 ms 207728 KB Output isn't correct
64 Halted 0 ms 0 KB -