結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー goodbatongoodbaton
提出日時 2016-11-09 19:24:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 57 ms / 5,000 ms
コード長 3,053 bytes
コンパイル時間 1,010 ms
コンパイル使用メモリ 86,672 KB
実行使用メモリ 11,408 KB
最終ジャッジ日時 2023-08-16 16:18:24
合計ジャッジ時間 2,537 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 29 ms
7,268 KB
testcase_10 AC 36 ms
4,376 KB
testcase_11 AC 20 ms
5,252 KB
testcase_12 AC 29 ms
7,320 KB
testcase_13 AC 7 ms
4,380 KB
testcase_14 AC 34 ms
11,396 KB
testcase_15 AC 57 ms
11,248 KB
testcase_16 AC 55 ms
11,240 KB
testcase_17 AC 56 ms
11,348 KB
testcase_18 AC 49 ms
11,288 KB
testcase_19 AC 44 ms
11,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


struct LazySeg_sum{
  
  struct Data{
    ll val;
    ll add;
    ll sum;
    bool valset;
    
    ll calc_sum(int l, int r){
      if(valset){
        return (val + add) * (r - l + 1);
      }else{
        return sum + add * (r - l + 1);
      }
    }

    void set_data(int x,int y){
      val = x;
      add = 0;
      valset = true;
    }
    
    Data():val(0),add(0),sum(0),valset(false){}
    
  };

  vector<Data> data;
  int seg_size;
  
  LazySeg_sum(int n){
    for(seg_size=1; seg_size < n; seg_size*=2);
    data.assign(seg_size*2, Data());
  }

  ll set(int a, int b, ll x, int l=0, int r=-1,int k = 0){
    if(r == -1) r = seg_size-1;
    
    if(a <= l && r <= b){
      data[k].set_data(x,0);
      return data[k].calc_sum(l,r);
    }

    if(r < a || b < l) return data[k].calc_sum(l,r);
    
    if(data[k].valset){
      data[k*2+1].set_data(data[k].val,data[k].add);
      data[k*2+2].set_data(data[k].val,data[k].add);
    }

    data[k].add = 0;
    
    data[k].valset = false;
    
    data[k].sum = set(a,b,x,l,(l+r)/2,k*2+1) + set(a,b,x,(l+r)/2+1,r,k*2+2);

    return data[k].calc_sum(l,r);
  }

  ll add(int a, int b, ll x, int l=0, int r=-1, int k = 0){
    if(r == -1) r = seg_size-1;

    if(a <= l && r <= b){
      data[k].add += x;
      return data[k].calc_sum(l,r);
    }

    if(r < a || b < l) return 0;

    if(data[k].valset){
      data[k*2+1].set_data(data[k].val,0);
      data[k*2+2].set_data(data[k].val,0);

      data[k].valset = false;
    }

    data[k].sum = add(a,b,x,l,(l+r)/2,k*2+1) + add(a,b,x,(l+r)/2+1,r,k*2+2);

    return data[k].calc_sum(l,r);
  }
  
  ll query(int a, int b, int l=0, int r=-1, int k = 0){
    if(r == -1) r = seg_size-1;

    if(r < a || b < l) return 0;

    if((a <= l && r <= b) || data[k].valset){
      return data[k].calc_sum(max(a,l),min(b,r));
    }

    return query(a,b,l,(l+r)/2,k*2+1) + query(a,b,(l+r)/2+1,r,k*2+2) +
           data[k].add * (min(b,r) - max(a,l) + 1);
  }
  
};

int main(){

  int n,q;
  int base = INF;
  ll A = 0, B = 0;
  
  scanf("%d%d",&n,&q);

  LazySeg_sum seg(n);
  
  for(int i=0;i<q;i++){
    int x,l,r;
    scanf("%d%d%d",&x,&l,&r);

    if( x == 1 ){
      seg.set(l,r,1);
    }

    if( x == 2 ){
      seg.set(l,r,base);
    }

    if( x == 0 ){
      ll val = seg.query(l,r);
      int a = val%base;
      int b = val/base;

      if( a > b ) A += a;
      if( b > a ) B += b;
    }

    //    debug(seg.query(0,INF));
  }

  ll val = seg.query(0,INF);
  A += val%base;
  B += val/base;

  printf("%lld %lld\n",A,B);
  
  return 0;
}
0