結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー tailstails
提出日時 2015-06-21 15:54:26
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 7 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 49 ms
5,376 KB
testcase_10 AC 71 ms
5,376 KB
testcase_11 AC 30 ms
5,376 KB
testcase_12 AC 52 ms
5,376 KB
testcase_13 AC 11 ms
5,376 KB
testcase_14 AC 67 ms
5,376 KB
testcase_15 AC 82 ms
5,376 KB
testcase_16 AC 91 ms
5,376 KB
testcase_17 AC 107 ms
5,376 KB
testcase_18 TLE -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

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