結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー tailstails
提出日時 2015-06-22 23:48:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 106 ms / 5,000 ms
コード長 2,303 bytes
コンパイル時間 2,724 ms
コンパイル使用メモリ 162,724 KB
実行使用メモリ 11,416 KB
最終ジャッジ日時 2023-09-21 23:49:55
合計ジャッジ時間 4,144 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,180 KB
testcase_01 AC 5 ms
11,236 KB
testcase_02 AC 5 ms
11,356 KB
testcase_03 AC 5 ms
11,256 KB
testcase_04 AC 5 ms
11,228 KB
testcase_05 AC 5 ms
11,296 KB
testcase_06 AC 11 ms
11,180 KB
testcase_07 AC 6 ms
11,384 KB
testcase_08 AC 7 ms
11,300 KB
testcase_09 AC 53 ms
11,416 KB
testcase_10 AC 80 ms
11,292 KB
testcase_11 AC 33 ms
11,184 KB
testcase_12 AC 54 ms
11,232 KB
testcase_13 AC 13 ms
11,364 KB
testcase_14 AC 76 ms
11,296 KB
testcase_15 AC 100 ms
11,408 KB
testcase_16 AC 103 ms
11,292 KB
testcase_17 AC 106 ms
11,296 KB
testcase_18 AC 95 ms
11,356 KB
testcase_19 AC 66 ms
11,412 KB
権限があれば一括ダウンロードができます

ソースコード

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