結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー pekempeypekempey
提出日時 2015-08-27 12:08:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,633 ms / 10,000 ms
コード長 3,704 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 175,452 KB
実行使用メモリ 225,048 KB
最終ジャッジ日時 2023-08-02 21:17:00
合計ジャッジ時間 28,341 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,633 ms
224,116 KB
testcase_01 AC 2,581 ms
224,664 KB
testcase_02 AC 2,532 ms
224,616 KB
testcase_03 AC 2,557 ms
223,736 KB
testcase_04 AC 2 ms
5,380 KB
testcase_05 AC 2,490 ms
224,552 KB
testcase_06 AC 2,441 ms
224,796 KB
testcase_07 AC 2,458 ms
223,656 KB
testcase_08 AC 2,469 ms
223,628 KB
testcase_09 AC 2,416 ms
225,048 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)’:
main.cpp:87:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) rep2 (i, 0, a)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) repr2 (i, 0, a)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

const ll mod = (ll)1e18 + 9;

ll weight[1010101];
ll wsum[1010101];
ll N, Q;
ll x[202020], l[202020], r[202020];

struct SegmentTree {
	int size;
	vector<ll> segt, lazyt;
	vector<bool> segr, lazyr;
	SegmentTree(int n) {
		size = 1;	
		while (size < n) size *= 2;
		segt.resize(size * 2 - 1);
		lazyt.resize(size * 2 - 1);
		segr.resize(size * 2 - 1);
		lazyr.resize(size * 2 - 1);
	}
	void evallazy(int k, int l, int r) {
		if (lazyr[k]) {
			segt[k] = 0;
		}
		segt[k] += lazyt[k] * (wsum[r] - wsum[l]);
		if (r - l > 1) {
			if (lazyr[k]) {
				lazyt[k * 2 + 1] = 0;
				lazyt[k * 2 + 2] = 0;
			}
			lazyr[k * 2 + 1] = lazyr[k] || lazyr[k * 2 + 1];
			lazyr[k * 2 + 2] = lazyr[k] || lazyr[k * 2 + 2];
			lazyt[k * 2 + 1] += lazyt[k];
			lazyt[k * 2 + 2] += lazyt[k];
		}
		lazyt[k] = 0;
		lazyr[k] = false;
	}
	// q=0:set, q=1:reset
	void update(int a, int b, int q, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			if (q == 0) {
				lazyt[k]++;
			} else {
				lazyt[k] = 0;
				lazyr[k] = true;
			}
			evallazy(k, l, r);
		} else {
			update(a, b, q, k * 2 + 1, l, (l + r) / 2);
			update(a, b, q, k * 2 + 2, (l + r) / 2, r);
			segt[k] = segt[k * 2 + 1] + segt[k * 2 + 2];
		}
	}
	void update(int a, int b, int q) {
		update(a, b, q, 0, 0, size);
	}
	ll query(int a, int b, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return 0;
		if (a <= l && r <= b) return segt[k];
		ll res = 0;
		res += query(a, b, k * 2 + 1, l, (l + r) / 2);
		res += query(a, b, k * 2 + 2, (l + r) / 2, r);
		return res;
	}
	ll query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
	ll query() {
		return query(0, size);
	}
};

template<class T1, class T2>
ostream &operator <<(ostream &os, const pair<T1, T2> &p) {
	cout << "(" << p.first << " " << p.second << ")";
}

template<class T>
ostream &operator <<(ostream &os, const vector<T> &v) {
	rep (i, v.size()) {
		if (i) cout << " ";
		cout << v[i];
	}
	return os;
}

int main() {
	cin >> N >> Q;
	rep (i, Q) {
		cin >> x[i] >> l[i] >> r[i];
	}
	if (Q == 0) {
		vector<ll> score(5);
		cout << score << endl;
		return 0;
	}
	vector<ll> xs;
	rep (i, Q) {
		xs.push_back(l[i]);
		xs.push_back(l[i] + 1);
		xs.push_back(r[i]);
		xs.push_back(r[i] + 1);
	}
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	ll w = xs.size();
	rep (i, xs.size() - 1) {
		weight[i] = xs[i + 1] - xs[i];
	}
	rep (i, Q) {
		l[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin();
		r[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin();
	}
	partial_sum(weight, weight + w, wsum + 1);

	// main logic
	// cout << "main logic" << endl;

	vector<SegmentTree> segt(5, SegmentTree(w + 10));
	vector<ll> score(5);
	rep (i, Q) {
		// cout << x[i] << " "	<< l[i] << " " << r[i] << endl;
		if (x[i] == 0) {
			vector<pair<ll, ll>> t(5);
			rep (j, 5) {
				t[j].second = j;
				t[j].first = segt[j].query(l[i], r[i] + 1);
			}
			sort(t.rbegin(), t.rend());
			// cout << "bonus" << endl;
			// cout << t << endl;
			if (t[0].first > t[1].first) {
				score[t[0].second] += t[0].first;
				score[t[0].second] %= mod;
			} else {
				// cout << "bad" << endl;
			}
		} else {
			x[i]--;
			rep (j, 5) {
				segt[j].update(l[i], r[i] + 1, x[i] != j);
			}
		}
		// cout << score << endl;
	}
	// cout << "end query" << endl;

	rep (i, 5) {
		score[i] += segt[i].query();
		score[i] %= mod;
	}

	cout << score << endl;

	return 0;
}
0