結果

問題 No.230 Splarraay スプラレェーイ
ユーザー goodbatongoodbaton
提出日時 2016-11-09 19:24:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 61 ms / 5,000 ms
コード長 3,053 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 85,168 KB
実行使用メモリ 11,540 KB
最終ジャッジ日時 2024-05-04 00:20:29
合計ジャッジ時間 1,865 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 5 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 30 ms
7,320 KB
testcase_10 AC 39 ms
5,376 KB
testcase_11 AC 21 ms
5,376 KB
testcase_12 AC 30 ms
7,296 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 35 ms
11,520 KB
testcase_15 AC 60 ms
11,520 KB
testcase_16 AC 58 ms
11,520 KB
testcase_17 AC 61 ms
11,392 KB
testcase_18 AC 50 ms
11,520 KB
testcase_19 AC 43 ms
11,540 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:131:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  131 |   scanf("%d%d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:137:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  137 |     scanf("%d%d%d",&x,&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

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