結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー goodbatongoodbaton
提出日時 2016-11-09 18:30:47
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,952 bytes
コンパイル時間 763 ms
コンパイル使用メモリ 85,272 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-05-04 00:19:07
合計ジャッジ時間 5,124 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 1 ms
5,376 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:128:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |   scanf("%d%d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:134:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  134 |     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;
    }

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

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

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

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