提出 #35152743

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 140000;
const int K = 4;
int a[N+10];
struct node{ // 维护 max[l..r] - min[l..r] + l - r
  int min; // 最小值
  int lazy; // lazy tag未向下传递的add
  array<int,K> cnt = {0,0,0,0}; // 最小值+0,+1,+2,+3出现的次数
}t[N*4+10];

// merge {min,count array}
pair<int,array<int,K>> merge(const pair<int,array<int,K> >&mc0,const pair<int,array<int,K>>&mc1){
  auto [m0,c0] = mc0;
  auto [m1,c1] = mc1;
  int m = min(m0,m1);
  array<int,K> c = {0,0,0,0};
  rep(i,0,K) if(m0+i<m+K) c[m0+i-m] += c0[i];
  rep(i,0,K) if(m1+i<m+K) c[m1+i-m] += c1[i];
  return {m,c};
}

void range_add(int o,int v){
  t[o].min+=v;
  t[o].lazy+=v;
}

void down(int o){
  if (!t[o].lazy) return;
  range_add(SEG_L,t[o].lazy);
  range_add(SEG_R,t[o].lazy);
  t[o].lazy=0;
}

void build(int o,int l,int r){
  if (l==r) {
    t[o].min = l;
    t[o].cnt[0] = 1;
    return;
  }
  build(SEG_L_CHILD);
  build(SEG_R_CHILD);
  tie(t[o].min,t[o].cnt) = merge({t[SEG_L].min,t[SEG_L].cnt},{t[SEG_R].min,t[SEG_R].cnt});
}

void add(int o, int l,int r,int ql,int qr,int v){
  if (ql <= l && r <= qr) return range_add(o,v);
  down(o);
  if (ql<=mid) add(SEG_L_CHILD,ql,qr,v);
  if (qr> mid) add(SEG_R_CHILD,ql,qr,v);
  tie(t[o].min,t[o].cnt) = merge({t[SEG_L].min,t[SEG_L].cnt},{t[SEG_R].min,t[SEG_R].cnt});
}

pair<int,array<int,K>> query(int o,int l,int r,int ql,int qr){ // {min, count array}
  if (ql <= l && r <= qr) return {t[o].min,t[o].cnt};
  down(o);
  auto ret = pair(0,array<int,K>{0,0,0,0}); // {min, count array}
  if (ql<=mid) ret = merge(ret,query(SEG_L_CHILD,ql,qr));
  if (qr> mid) ret = merge(ret,query(SEG_R_CHILD,ql,qr));
  return ret;
}

int main(){
  int n = read();
  int k = read();
  rep(i,0,n) a[i] = read();

  build(SEG_ROOT);
  ll ans = 0;
  vector<int> mx; // 区间最大值 下标, 单调递减栈 维护
  vector<int> mn; // 区间最小值 下标, 单调递增栈 维护
  rep(i,0,n){
    for(;mx.size()&&a[mx.back()]<a[i];mx.pop_back())add(SEG_ROOT,mx.size()>1?mx[mx.size()-2]+1:0,mx.back(),a[i]-a[mx.back()]); // [a[mx.size()-2]+1...a[mx.back()]] 全部增量
    mx.push_back(i);
    for(;mn.size()&&a[mn.back()]>a[i];mn.pop_back())add(SEG_ROOT,mn.size()-1?mn[mn.size()-2]+1:0,mn.back(),a[mn.back()]-a[i]);
    mn.push_back(i);
    auto [_,c] = query(SEG_ROOT,0,i);
    rep(j,0,k+1) ans += c[j];
    add(SEG_ROOT,0,n-1,-1); // r增加, 全部-1
  }
  printf("%lld\n",ans);
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘ll read()’:
./Main.cpp:14:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   14 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果