結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー antaanta
提出日時 2015-07-24 23:37:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 768 ms / 10,000 ms
コード長 8,104 bytes
コンパイル時間 1,638 ms
コンパイル使用メモリ 108,328 KB
実行使用メモリ 63,232 KB
最終ジャッジ日時 2024-04-20 21:11:56
合計ジャッジ時間 9,310 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 768 ms
63,104 KB
testcase_01 AC 745 ms
63,104 KB
testcase_02 AC 663 ms
63,100 KB
testcase_03 AC 543 ms
62,980 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 667 ms
63,108 KB
testcase_06 AC 673 ms
63,100 KB
testcase_07 AC 667 ms
63,232 KB
testcase_08 AC 673 ms
63,232 KB
testcase_09 AC 658 ms
63,108 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:244:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  244 |                         scanf("%d%lld%lld", &x, &l, &r), ++ r;
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct ModInt {
	static const ll Mod;
	long long x;
	ModInt(): x(0) { }
	ModInt(signed sig) { ll sigt = sig % Mod; if(sigt < 0) sigt += Mod; x = sigt; }
	ModInt(signed long long sig) { ll sigt = sig % Mod; if(sigt < 0) sigt += Mod; x = sigt; }
	ll get() const { return x; }
	
	ModInt &operator+=(ModInt that) { if((x += that.x) >= Mod) x -= Mod; return *this; }
	
	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
};
const ll ModInt::Mod = (ll)1e18+9;
typedef ModInt mint;

const int K = 5;
struct Val {
	int team, val;
	ll size;
	Val(): team(0), val(0), size(0) { }
	Val(int t, int v, ll s): team(t), val(v), size(s) { }
};
struct Sum {
	ll sums[K];
	ll size;
	Sum() { rep(k, K) sums[k] = 0; size = 0; }
	Sum(const Val &val, int pos) {
		rep(k, K) sums[k] = 0;
		sums[val.team] = (ll)val.val * val.size;
		size = val.size;
	}
	Sum &operator+=(const Sum &that) {
		rep(k, K) sums[k] += that.sums[k];
		size += that.size;
		return *this;
	}
	Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};

struct Add {
	bool a; bool clr; Val x;
	Add(): a(false), clr(false), x() { }
	explicit Add(Val c): a(true), clr(false), x(c) { }
	Add &operator+=(const Add &that) {
		if(that.a) {
			if(!a) {
				*this = that;
			}else if(x.team == that.x.team && !that.clr) {
//				clr = clr;
				x.val += that.x.val;
			}else {
				clr = true;
				x = that.x;
			}
		}
		return *this;
	}
	void addToVal(Val &val, int pos) const {
		if(a) {
			if(clr) val.val = 0;
			if(val.team == x.team) {
				val.val += x.val;
			}else {
				val.team = x.team;
				val.val = x.val;
			}
		}
	}
	void addToSum(Sum &sum, int left, int right) const {
		if(a) {
			rep(k, K) if(k != x.team) sum.sums[k] = 0;
			if(clr) sum.sums[x.team] = 0;
			sum.sums[x.team] += (ll)sum.size * x.val;
		}
	}
};

struct SegmentTree {
	vector<Val> leafs;
	vector<Sum> nodes;
	vector<Add> add;
	vector<int> leftpos, rightpos;
	int n, n2;
	void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
	void init(const vector<Val> &u) {
		n = 1; while(n < (int)u.size()) n *= 2;
		n2 = (n - 1) / 2 + 1;
		leafs = u; leafs.resize(n, Val());
		nodes.resize(n);
		for(int i = n-1; i >= n2; -- i)
			nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n);
		for(int i = n2-1; i > 0; -- i)
			nodes[i] = nodes[i*2] + nodes[i*2+1];
		add.assign(n, Add());

		leftpos.resize(n); rightpos.resize(n);
		for(int i = n-1; i >= n2; -- i) {
			leftpos[i] = i*2-n;
			rightpos[i] = (i*2+1-n) + 1;
		}
		for(int i = n2-1; i > 0; -- i) {
			leftpos[i] = leftpos[i*2];
			rightpos[i] = rightpos[i*2+1];
		}
	}
	Val get(int i) {
		int indices[128];
		int k = getIndices(indices, i, i+1);
		propagateRange(indices, k);
		return leafs[i];
	}
	Sum getRangeCommutative(int i, int j) {
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		Sum res = Sum();
		for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) res += sum(l ++);
			if(r & 1) res += sum(-- r);
		}
		return res;
	}
	Sum getRange(int i, int j) {
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		Sum res = Sum();
		for(; i && i + (i&-i) <= j; i += i&-i)
			res += sum((n+i) / (i&-i));
		for(k = 0; i < j; j -= j&-j)
			indices[k ++] = (n+j) / (j&-j) - 1;
		while(-- k >= 0) res += sum(indices[k]);
		return res;
	}
	void set(int i, const Val &x) {
		int indices[128];
		int k = getIndices(indices, i, i+1);
		propagateRange(indices, k);
		leafs[i] = x;
		mergeRange(indices, k);
	}
	void addToRange(int i, int j, const Add &x) {
		if(i >= j) return;
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		int l = i + n, r = j + n;
		if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
		if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
		for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) add[l ++] += x;
			if(r & 1) add[-- r] += x;
		}
		mergeRange(indices, k);
	}
private:
	int getIndices(int indices[], int i, int j) const {
		int k = 0, l, r;
		if(i >= j) return 0;
		for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
			indices[k ++] = l;
			indices[k ++] = r;
		}
		for(; l; l >>= 1) indices[k ++] = l;
		return k;
	}
	void propagateRange(int indices[], int k) {
		for(int i = k - 1; i >= 0; -- i)
			propagate(indices[i]);
	}
	void mergeRange(int indices[], int k) {
		for(int i = 0; i < k; ++ i)
			merge(indices[i]);
	}
	inline void propagate(int i) {
		if(i >= n) return;
		add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
		if(i * 2 < n) {
			add[i * 2] += add[i];
			add[i * 2 + 1] += add[i];
		}else {
			add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
			add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
		}
		add[i] = Add();
	}
	inline void merge(int i) {
		if(i >= n) return;
		nodes[i] = sum(i * 2) + sum(i * 2 + 1);
	}
	inline Sum sum(int i) {
		propagate(i);
		return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
	}
};


int main() {
	ll N; int Q;
	while(cin >> N >> Q) {
		typedef pair<ll,ll> pll;
		vector<pair<int,pll> > queries(Q);
		vector<ll> values;
		rep(ii, Q) {
			int x; ll l, r;
//			x=rand()%6,l=rand()%N,r=rand()%N;if(l>r)swap(l,r);++r;
			scanf("%d%lld%lld", &x, &l, &r), ++ r;
			queries[ii] = mp(x, mp(l, r));
			values.push_back(l);
			values.push_back(r);
		}
		sort(all(values)); values.erase(unique(all(values)), values.end());
		int X = values.size();
		SegmentTree segt;
		vector<Val> initval(X);
		rep(i, X-1) initval[i] = Val(0, 0, values[i+1] - values[i]);
		segt.init(initval);
		mint pts[K] = {};
//		vector<Val> naiveval((int)N);
		rep(ii, Q) {
			int x = queries[ii].first;
			ll L = queries[ii].second.first;
			ll R = queries[ii].second.second;
			int l = lower_bound(all(values), L) - values.begin();
			int r = lower_bound(all(values), R) - values.begin();;
			if(x == 0) {
				Sum sum = segt.getRangeCommutative(l, r);
				int k = max_element(sum.sums, sum.sums + K) - sum.sums;
				if(count(sum.sums, sum.sums + K, sum.sums[k]) == 1)
					pts[k] += sum.sums[k];
//				ll naivesum[K]={};
//				reu(i,(int)L,(int)R)naivesum[naiveval[i].team]+=naiveval[i].val;
//				rep(i,K)if(sum.sums[i]!=naivesum[i])
//					cerr<<sum.sums[i]<<" != "<<naivesum[i]<<endl;
			}else if(x <= 5) {
				segt.addToRange(l, r, Add(Val(x-1, 1, 0)));

//				reu(i, (int)L, (int)R)
//					Add(Val(x-1, 1, 0)).addToVal(naiveval[i], -1);
			}else return 0;
//			Sum sum = segt.getRangeCommutative(0, X);
//			rep(l, K) cerr << sum.sums[l] << ", "; cerr << endl;
//			ll naivesum[K]={};
//			reu(i,0,(int)N)naivesum[naiveval[i].team]+=naiveval[i].val;
//			rep(i,K)if(sum.sums[i]!=naivesum[i])
//				cerr<<sum.sums[i]<<" != "<<naivesum[i]<<endl;
		}
		Sum sum = segt.getRangeCommutative(0, X);
		rep(k, K)
			pts[k] += sum.sums[k];
		cout << pts[0].get() << " " << pts[1].get() << " " << pts[2].get() << " " << pts[3].get() << " " << pts[4].get() << endl;
		break;
	}
	return 0;
}
0