提出 #4298552

---

ソースコード 拡げる

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

struct query{
  int type;//0=empty, 1=add-sum ,2=set-min
  ll value;
  query(int a=0,ll b=0):type(a),value(b) {}
};

ll INF=(1LL<<60);

struct segtree{
  int SIZE;
  vector<query> s;
  vector<ll> t;// sum-add
  vector<ll> u;// min-set

  segtree(int n=1){
    SIZE=1;
    while(SIZE<n)SIZE*=2;
    s.clear();
    t.clear();
    u.clear();
    s.resize(SIZE*2, query());
    t.resize(SIZE*2, 0);
    u.resize(SIZE*2, 0);
  }
  
  void func(int k,int l,int r,query q){
    if(q.type==1){
      if(s[k].type==0)s[k]=q;
      else s[k].value+=q.value;
      t[k]+=q.value*(r-l);
      u[k]+=q.value;
    }
    if(q.type==2){
      s[k]=q;
      t[k]=q.value*(r-l);
      u[k]=q.value;
    }
  }

  void compute(int k,int l,int r){
    query q=s[k];
    s[k]=query();
    if(q.type==0||r-l==1)return;
    int m=(l+r)/2;
    func(k*2+1,l,m,q);
    func(k*2+2,m,r,q);
  }

  void Update(int a,int b,query x,int k,int l,int r){
    if(b<=l || r<=a)return;
    compute(k,l,r);
    if(a<=l && r<=b){
      func(k,l,r,x);
    }else{
      int m=(l+r)/2;
      Update(a,b,x,k*2+1,l,m);
      Update(a,b,x,k*2+2,m,r);
      t[k]=t[k*2+1]+t[k*2+2];
      u[k]=min(u[k*2+1],u[k*2+2]);
    }
  }

  ll Dfs(int type,int a,int b,int k,int l,int r){
    if(b<=l || r<=a){
      if(type==1)return 0; //add
      if(type==2)return INF; // min
    }
    compute(k,l,r);
    if(a<=l && r<=b){
      if(type==1)return t[k];
      if(type==2)return u[k];
    }else{
      int m=(l+r)/2;
      ll lv=Dfs(type,a,b,k*2+1,l,m);
      ll rv=Dfs(type,a,b,k*2+2,m,r);
      if(type==1)return lv+rv; // add
      if(type==2)return min(lv,rv); // min
    }
  }

  void Add(int a,int b,ll x){
    Update(a,b,query(1,x), 0,0,SIZE);
  }
  void Set(int a,int b,ll x){
    Update(a,b,query(2,x), 0,0,SIZE);
  }
  ll Getsum(int a,int b){
    return Dfs(1,a,b, 0,0,SIZE);
  }
  ll Getmin(int a,int b){
    return Dfs(2,a,b, 0,0,SIZE);
  }
  
};


ll N,M;
segtree T(200005);

int main(){
  cin>>N>>M;
  ll total=0;
  ll last=0;
  for(int i=0;i<M;i++){
    ll t,l,r;
    cin>>t>>l>>r;
    T.Add(0,N+1,t-last);
    ll ans=T.Getsum(l-1,r);
    total+=ans;
    T.Set(l-1,r,0);

    last=t;
  }
  cout<<total<<endl;
  return 0;
}

提出情報

ジャッジ結果