結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー btk
提出日時 2015-06-20 03:41:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 306 ms / 5,000 ms
コード長 3,904 bytes
コンパイル時間 571 ms
コンパイル使用メモリ 88,316 KB
実行使用メモリ 134,600 KB
最終ジャッジ日時 2024-07-07 04:37:13
合計ジャッジ時間 4,167 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
#define SZ 1048576
typedef pair<int, int> P;
typedef long long LL;
#define st(x) (x).first
#define ed(x) (x).second


struct seg_Tree{
	P interval;//その区間の長さ
	LL child;//子供区間の合計値
	LL val;//その区間全体に対して更新された値
	bool update;//全て同じ値かどうか
	int size(){ return(ed(interval) - st(interval) + 1); }
	void set(int s, int t){
		st(interval) = s, ed(interval) = t;
	}
	seg_Tree(){
		val = child=0;
		update = false;
		set(1, 0);
	}
};

seg_Tree table[SZ*2+1];
seg_Tree used[SZ*2+1];
void make_tree(seg_Tree* tree,int k, int s, int t){
	//	if(k>SZ*2)printf("%d[%d,%d]\n", k, s, t);
	if (s <= t){
		tree[k].set(s, t);
		if (tree[k].size() > 1){
			int l = 2 * k + 1;
			int r = l + 1;
			make_tree(tree,l, s, (s + t) / 2);
			make_tree(tree,r, (s + t) / 2 + 1, t);
		}
	}
}


LL get(seg_Tree* tree, int k, P len){
	int l = 2 * k + 1;//左の子
	int r = l + 1;//右の子
	if (tree[k].interval == len){
		return tree[k].val*tree[k].size()+tree[k].child;
	}
	//遅延評価
	if (tree[k].update){
		tree[l].val = tree[k].val; tree[l].child = 0;
		tree[r].val = tree[k].val; tree[r].child = 0;
		tree[l].update = tree[r].update = true;
	}
	tree[k].update = false;
	tree[k].val = 0;

	LL ret;
	//真ん中より左側
	if (ed(len) <= ed(tree[l].interval)){
		ret =get(tree, l, len);
	}

	//真ん中より右側
	else if ((st(len) >= st(tree[r].interval))){
		ret = get(tree, r, len);
	}

	//そうでない
	else ret = get(tree, l, make_pair(st(len), ed(tree[l].interval))) + get(tree, r, make_pair(st(tree[r].interval), ed(len)));
	tree[k].child = get(tree, l, tree[l].interval) + get(tree, r, tree[r].interval);
	return ret;

}
LL add(seg_Tree* tree, int k, P len, LL val){
//	printf("[%d,%d][%d,%d](%lld)\n", st(tree[k].interval), ed(tree[k].interval), st(len), ed(len), val);
	int l = 2 * k + 1;//左の子
	int r = l + 1;//右の子
	//区間ぴったし
	if (tree[k].interval == len){
		tree[k].val = val; 
		tree[k].child = 0; 
		tree[k].update = true;
		return tree[k].val*tree[k].size();
	}

	//遅延評価
	if (tree[k].update){
		tree[l].val =tree[k].val; tree[l].child = 0;
		tree[r].val =tree[k].val; tree[r].child = 0;
		tree[l].update = tree[r].update = true;
	}
	tree[k].update = false;
	tree[k].val = 0;

	//真ん中より左側
	if (ed(len) <= ed(tree[l].interval)){
		return	tree[k].child = add(tree, l, len, val) + get(tree, r, tree[r].interval);
	}
	
	//真ん中より右側
	if ((st(len) >= st(tree[r].interval)))
		return tree[k].child = add(tree, r, len, val) + get(tree, l, tree[l].interval);
	
	//そうでない
	return tree[k].child = add(tree, l, make_pair(st(len), ed(tree[l].interval)), val)+add(tree, r, make_pair(st(tree[r].interval), ed(len)), val);

}

int main(void){

	int N,Q;
	LL A = 0,B = 0;
	make_tree(table, 0, 0, SZ);
	make_tree(used, 0, 0, SZ);
	cin >> N >> Q;
	for (int i = 0; i < Q; i++){
		int x, l, r;
		cin >> x >> l >> r;
		switch (x){
		case 0:
		{
			LL dist = get(table, 0, make_pair(l, r));
			LL n = get(used, 0, make_pair(l, r));
			if (dist>0)A += (n + dist)/2;
			else if (dist < 0)B += (n - dist)/2;
		}
		break;
		case 1:
		{
			add(table, 0, make_pair(l, r), 1);
			add(used, 0, make_pair(l, r), 1);
		}
		break;
		case 2:
		{
			add(table, 0, make_pair(l, r), -1);
			add(used, 0, make_pair(l, r), 1);
		}
		break;
		default:
			break;
		}
	//	cout << table[0].child << endl;
	}
	LL dist = get(table, 0, make_pair(0, N-1));
	LL n = get(used, 0, make_pair(0, N-1));
	A += (n + dist)/2;
	B += (n - dist)/2;
	cout << A << " " << B << endl;
	return(0);
}
0