結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー tails
提出日時 2015-06-21 15:54:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,638 bytes
コンパイル時間 1,269 ms
コンパイル使用メモリ 165,000 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-07-07 15:48:21
合計ジャッジ時間 8,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class SegTree {
public:

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

	~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:

	char * mpNode;
	int mN;

	void fill( int l, int r, int v, int ni, int nl, int w ) {
		char * p = mpNode + ni;
		if( v == *p ) {
			return;
		}
		if( l == nl && r == nl+w-1 ) {
			*p = v;
			return;
		}
		char * c0 = mpNode + (ni*2+1);
		char * c1 = c0 + 1;
		if( *p >= 0 ) {
			*c0 = *p;
			*c1 = *p;
			*p = -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 );
		}
		if( *c0 == *c1 ) {
			*p = *c0;
		}
	}

	int count( int l, int r, int v, int ni, int nl, int w ) {
		char * p = mpNode + ni;
		if( *p >= 0 ) {
			return *p == v ? r-l+1 : 0;
		} 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