#39355 (C++11) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

提出ソース

結果

問題	No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー	koyumeishi
提出日時	2015-07-25 09:44:53
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	6,788 bytes
コンパイル時間	1,433 ms
コンパイル使用メモリ	108,156 KB
実行使用メモリ	30,796 KB
最終ジャッジ日時	2023-09-23 04:43:33
合計ジャッジ時間	3,768 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 8,924 KB
testcase_01	AC	4 ms 8,984 KB
testcase_02	AC	4 ms 8,972 KB
testcase_03	AC	3 ms 8,908 KB
testcase_04	AC	5 ms 9,112 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	45 ms 9,228 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	93 ms 30,796 KB
testcase_19	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;

struct node{	//[l,r)
	long long lb;
	long long ub;
	node* left;
	node* right;
	long long val;
	long long lazy;
	bool is_lazy;
	bool zero_fill;
	node() : 
		lb(0), ub(0),
		left(nullptr), right(nullptr),
		val(0), lazy(0),
		is_lazy(false),
		zero_fill(false)
	{
	}

	node(long long l, long long r, long long v, long long u) : 
		lb(l), ub(r),
		left(nullptr), right(nullptr),
		val(v), lazy(u),
		is_lazy(false),
		zero_fill(false)
	{
	}
};

vector<vector<node>*> pool;
int table_size = 100000;
int pool_ptr;


//V := type of node value
//U := type of lazy value
template<class V=int, class U=int>
class Dynamic_SegmentTree{

	//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;
	}
	V evaluate_vl(node* t){
		V ret = default_v;
		if(t->is_lazy){
			ret = t->val + t->lazy * (t->ub - t->lb);
		}else{
			ret = t->val;
		}

		return ret;
	}


	void set_children(node* t){
		if(t->left == nullptr){

			if(pool_ptr == 0){
				pool.push_back(new vector<node>(table_size));
			}
			t->left = &pool.back()->at(pool_ptr++);
			t->left->lb = t->lb;
			t->left->ub = (t->lb+t->ub) / 2;
			if(pool_ptr == table_size) pool_ptr -= table_size;


			if(pool_ptr == 0){
				pool.push_back(new vector<node>(table_size));
			}
			t->right = &pool.back()->at(pool_ptr++);
			t->right->lb = (t->lb+t->ub) / 2;
			t->right->ub = t->ub;
			if(pool_ptr == table_size) pool_ptr -= table_size;

			//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);
		}
	}

	void zero_propagete(node* t){
		if(t->zero_fill){
			t->zero_fill = false;

			if(t->ub - t->lb == 1){
				return;
			}

			set_children(t);
			for(node* ch : {t->left, t->right}){

				ch->val = default_v;
				ch->lazy = default_l;
				ch->is_lazy = false;
				ch->zero_fill = true;
			}
		}
	}

	void propagete(node* t){
		zero_propagete(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;
		}
		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));
	}


	void range_update_zero(node* t, long long lb, long long ub){
		if(ub <= t->lb || t->ub <= lb) return;	//out of range
		propagete(t);

		if(lb <= t->lb && t->ub <= ub){	// fully covered
			t->zero_fill = true;
			t->val = default_v;
			t->lazy = default_l;
			t->is_lazy = false;
			
			//t->val = default_v;	//range fill
			return;
		}
		set_children(t);

		range_update_zero(t->left, lb,ub);
		range_update_zero(t->right, lb,ub);

		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);
		}
		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;

		if(pool_ptr == 0){
			pool.push_back(new vector<node>(table_size));
		}
		root = &pool.back()->at(pool_ptr++);
		root->lb = 0;
		root->ub = sz;
		if(pool_ptr == table_size) pool_ptr -= table_size;

		//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);
	}


	void range_update_zero(long long lb, long long ub){
		range_update_zero(root, lb, ub);
	}


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

};

#define MOD 1000000000000000009

int main(){
	long long n,q;
	scanf("%lld%lld", &n,&q);
	int team = 2;

	//pool.push_back(new vector<node*>(100000));
	pool_ptr = 0;

	Dynamic_SegmentTree<long long, long long> a(n+1);
	Dynamic_SegmentTree<long long, long long> b(n+1);
	Dynamic_SegmentTree<long long, long long> c(n+1);
	Dynamic_SegmentTree<long long, long long> d(n+1);
	Dynamic_SegmentTree<long long, long long> e(n+1);

	vector<unsigned long long> ans(5,0);
	vector<Dynamic_SegmentTree<long long, long long>*> seg(5);
	seg[0] = &a;
	seg[1] = &b;
	seg[2] = &c;
	seg[3] = &d;
	seg[4] = &e;

	for(int i=0; i<q; i++){
		long long x,l,r;
		scanf("%lld%lld%lld", &x,&l,&r);

		if(x==0){
			vector<unsigned long long> cnt(5,0);
			unsigned long long my_max = 0;
			for(int j=0; j<team; j++){
				cnt[j] = seg[j]->range_evaluate(l,r+1);
				my_max = max(my_max, cnt[j]);
			}
			vector<int> max_ele;
			for(int j=0; j<team; j++){
				if(cnt[j] == my_max) max_ele.push_back(j);
			}

			if(max_ele.size() != 1) continue;
			ans[max_ele[0]] += my_max;

			if(ans[max_ele[0]] >= MOD) ans[max_ele[0]] -= MOD;

		}else{
			for(int j=0; j<team; j++){
				if(j==x-1) seg[j]->range_update(l,r+1, 1);
				else seg[j]->range_update_zero(l,r+1);
			}
		}
	}

	for(int i=0; i<team; i++){
		unsigned long long cnt = seg[i]->range_evaluate(0,n);
		ans[i] += cnt;
		if(ans[i] >= MOD) ans[i] -= MOD;
		cout << ans[i] << (i==4?"\n":" ");
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード