結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー tails
提出日時 2015-06-22 23:48:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 95 ms / 5,000 ms
コード長 2,303 bytes
コンパイル時間 1,446 ms
コンパイル使用メモリ 165,012 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-07-07 16:44:45
合計ジャッジ時間 2,983 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class SegTree {
public:

	SegTree(int height){
		mN = 1 << height;
		mpNode = new Node[mN*2-1];
		memset( mpNode, 0, sizeof(Node) * (mN*2-1) );
		mpNode[0].count[0] = mN;
	}

	~SegTree() {
		delete[] mpNode;
	}

	void fill( int l, int r, int v ){
		fill( l, r, v, 0, 0, mN );
	}

	int count( int l, int r, int v ){
		return count( l, r, v, 0, 0, mN );
	}

private:

	struct Node {
		int value;
		int count[3];
	};
	Node * mpNode;
	int mN;

	void fill( int l, int r, int v, int ni, int nl, int w ) {
		Node * p = mpNode + ni;
		if( v == p->value ) {
			return;
		}
		if( l == nl && r == nl+w-1 ) {
			p->value = v;
			p->count[0] = v==0 ? w : 0;
			p->count[1] = v==1 ? w : 0;
			p->count[2] = v==2 ? w : 0;
			return;
		}
		Node * c0 = mpNode + (ni*2+1);
		Node * c1 = c0 + 1;
		if( p->value >= 0 ) {
			c0->value = p->value;
			c0->count[0] = c0->value == 0 ? w/2 : 0;
			c0->count[1] = c0->value == 1 ? w/2 : 0;
			c0->count[2] = c0->value == 2 ? w/2 : 0;
			c1->value = p->value;
			c1->count[0] = c1->value == 0 ? w/2 : 0;
			c1->count[1] = c1->value == 1 ? w/2 : 0;
			c1->count[2] = c1->value == 2 ? w/2 : 0;
			p->value = -1;
		}
		if( l < nl+w/2 ) {
			fill( l, min(nl+w/2-1,r), v, ni*2+1, nl, w/2 );
		}
		if( r >= nl+w/2 ) {
			fill( max(l,nl+w/2), r, v, ni*2+2, nl+w/2, w/2 );
		}
		p->count[0] = c0->count[0] + c1->count[0];
		p->count[1] = c0->count[1] + c1->count[1];
		p->count[2] = c0->count[2] + c1->count[2];
	}

	int count( int l, int r, int v, int ni, int nl, int w ) {
		Node * p = mpNode + ni;
		if( p->value >= 0 ) {
			return p->value == v ? r-l+1 : 0;
		} else if( l==nl && r==nl+w-1 ) {
			return p->count[v];
		} else {
			int result = 0;
			if( l < nl+w/2 ) {
				result += count( l, min(nl+w/2-1,r), v, ni*2+1, nl, w/2 );
			}
			if( r >= nl+w/2 ) {
				result += count( max(l,nl+w/2), r, v, ni*2+2, nl+w/2, w/2 );
			}
			return result;
		}
	}
	
};

int N,Q;

int main() {
	cin >> N >> Q;
	long long a=0,b=0;
	SegTree st(18);
	for(int i=0; i<Q; ++i){
		int x,l,r;
		cin >> x >> l >> r;
		if(x==0){
			int ta = st.count(l,r,1);
			int tb = st.count(l,r,2);
			if(ta>tb) a+=ta;
			if(ta<tb) b+=tb;
		}else{
			st.fill(l,r,x);
		}
	}
	a += st.count(0,N-1,1);
	b += st.count(0,N-1,2);
	cout << a << " " << b << endl;
	return 0;
}
0