結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー goodbaton
提出日時 2016-11-09 18:42:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,045 bytes
コンパイル時間 630 ms
コンパイル使用メモリ 86,564 KB
実行使用メモリ 11,572 KB
最終ジャッジ日時 2024-11-25 05:54:53
合計ジャッジ時間 1,820 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 3 WA * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:130:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  130 |   scanf("%d%d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:136:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  136 |     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);
      }
    }
    
    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].val = x;
      data[k].add = 0;
      data[k].valset = true;
      return data[k].calc_sum(l,r);
    }

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

    data[k*2+1].add += data[k].add;
    data[k*2+2].add += data[k].add;

    if(data[k].valset){
      data[k*2+1].val += data[k].val;
      data[k*2+2].val += data[k].val;
      data[k*2+1].valset = true;
      data[k*2+2].valset = true;

      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].val += data[k].val;
      data[k*2+2].val += data[k].val;
      data[k*2+1].valset = true;
      data[k*2+2].valset = true;

      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(a <= l && r <= b) return data[k].calc_sum(l,r);
    if(r < a || b < l) return 0;

    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<n;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;
    }
  }

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

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