結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー koyumeishikoyumeishi
提出日時 2015-07-25 05:01:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 313 ms / 5,000 ms
コード長 4,438 bytes
コンパイル時間 836 ms
コンパイル使用メモリ 80,572 KB
実行使用メモリ 31,184 KB
最終ジャッジ日時 2024-07-16 04:39:01
合計ジャッジ時間 3,512 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 12 ms
6,940 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 138 ms
16,728 KB
testcase_10 AC 88 ms
6,940 KB
testcase_11 AC 72 ms
11,864 KB
testcase_12 AC 133 ms
16,720 KB
testcase_13 AC 18 ms
6,944 KB
testcase_14 AC 66 ms
6,944 KB
testcase_15 AC 127 ms
6,944 KB
testcase_16 AC 207 ms
16,728 KB
testcase_17 AC 313 ms
30,544 KB
testcase_18 AC 153 ms
31,184 KB
testcase_19 AC 189 ms
27,860 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
using namespace std;

//V := type of node value
//U := type of lazy value
template<class V=int, class U=int>
class Dynamic_SegmentTree{
	struct node{	//[l,r)
		long long lb;
		long long ub;
		node* left;
		node* right;
		V val;
		U lazy;
		bool is_lazy;
		node(long long l, long long r, U v, U u) : 
			lb(l), ub(r),
			left(nullptr), right(nullptr),
			val(v), lazy(u),
			is_lazy(false)
		{
		}
	};

	vector<node*> pool;
	node* root;
	V default_v;
	U default_l;

	//range add
	V evaluate_vv(V a, V b){
		return a+b;
	}
	U evaluate_ll(U a, U b){
		//return a+b;
		 return b; //range fill
	}
	V evaluate_vl(node* t){
		if(t->ub - t->lb == 1){
			if(t->is_lazy) return t->lazy;
			return t->val;
		}else{
			if(t->is_lazy) return t->val + t->lazy * (t->ub - t->lb);
			return t->val;
		}
	}


	inline void set_children(node* t){
		if(t->left == nullptr){
			t->left = new node(t->lb, (t->lb+t->ub)/2, default_v, default_l);
			t->right = new node((t->lb+t->ub)/2, t->ub, default_v, default_l);

			pool.push_back(t->left);
			pool.push_back(t->right);

		}
	}

	void propagete(node* t){
		if(t->is_lazy == false) return;
		if(t->ub - t->lb == 1){
			t->val = evaluate_vl(t);
		}else{
			set_children(t);
			for(node* ch : {t->left, t->right}){
				if(ch->is_lazy){
					ch->lazy = evaluate_ll(ch->lazy, t->lazy);
				}else{
					ch->lazy = t->lazy;
				}
				ch->is_lazy = true;

				ch->val = default_v;	//range fill
			}

		}

		t->lazy = default_l;
		t->is_lazy = false;
		if(t->left != nullptr) t->val = evaluate_vv(evaluate_vl(t->left), evaluate_vl(t->right));
	}

	void range_update(node* t, long long lb, long long ub, U new_val){
		if(ub <= t->lb || t->ub <= lb) return;	//out of range
		propagete(t);
		if(lb <= t->lb && t->ub <= ub){	// fully covered
			t->lazy = new_val;
			t->is_lazy = true;
			
			t->val = default_v;	//range fill
			return;
		}

		//partially covered
		set_children(t);

		range_update(t->left, lb,ub, new_val);
		range_update(t->right, lb,ub, new_val);

		t->val = evaluate_vv(evaluate_vl(t->left), evaluate_vl(t->right));
	}

	V range_evaluate(node* t, long long lb, long long ub){

		if(ub <= t->lb || t->ub <= lb) return default_v;	//out of range
		propagete(t);

		if(lb <= t->lb && t->ub <= ub){	// fully covered
			return evaluate_vl(t);
		}

		//partially covered
		set_children(t);

		V l_val = range_evaluate(t->left, lb,ub);
		V r_val = range_evaluate(t->right, lb,ub);
		return evaluate_vv(l_val, r_val);
	}

public:
	Dynamic_SegmentTree(long long size, V default_value=0, U default_lazy=0) :
		default_v(default_value), default_l(default_lazy)
	{
		long long sz = 1;
		while(sz < size) sz <<= 1LL;

		root = new node(0,sz, default_value, default_lazy);
		pool.push_back(root);
	}

	~Dynamic_SegmentTree(){
		for(int i=0; i<pool.size(); i++){
			delete(pool[i]);
		}
	}

	// A[pos] <- set_val
	void update(long long pos, V set_val){
		node* t = root;
		stack<node*> s;
		s.push(t);
		while(t->ub - t->lb != 1){
			set_children(t);
			propagete(t);

			if ( pos < (t->ub + t->lb) / 2 ){
				t = t->left;
			}else{
				t = t->right;
			}
			s.push(t);
		}

		propagete(t);
		s.top() -> val = set_val;
		s.pop();

		while(s.size()){
			t = s.top();
			s.pop();
			t->val = evaluate_vv(evaluate_vl(t->left), evaluate_vl(t->right));
		}
	}

	void range_update(long long lb, long long ub, U new_val){
		range_update(root, lb, ub, new_val);
	}

	V range_evaluate(long long lb, long long ub){
		return range_evaluate(root, lb, ub);
	}

	void dbg(){
		for(auto t: pool){
			cerr << "[ " << t->lb << " - " << t->ub  << " ) : " << t->val << " " << t->lazy << endl;
		}
	}
};


int main(){
	int n,q;
	cin >> n >> q;
	Dynamic_SegmentTree<int> a(n);
	Dynamic_SegmentTree<int> b(n);

	long long ans_a = 0;
	long long ans_b = 0;

	for(int i=0; i<q; i++){
		int x,l,r;
		cin >> x >> l >> r;
		if(x==0){
			int cnt_a = a.range_evaluate(l,r+1);
			int cnt_b = b.range_evaluate(l,r+1);

			if(cnt_a == cnt_b) continue;
			(cnt_a>cnt_b?ans_a:ans_b) += max(cnt_a, cnt_b);

		}else{
			a.range_update(l,r+1, x==1?1:0);
			b.range_update(l,r+1, x==1?0:1);
		}
	}

	int cnt_a = a.range_evaluate(0,n);
	int cnt_b = b.range_evaluate(0,n);

	ans_a += cnt_a;
	ans_b += cnt_b;

	cout << ans_a << " " << ans_b << endl;
	return 0;
}
0