結果
問題 | No.255 Splarrraaay スプラーレェーーイ |
ユーザー |
|
提出日時 | 2015-08-27 12:08:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,711 ms / 10,000 ms |
コード長 | 3,704 bytes |
コンパイル時間 | 1,920 ms |
コンパイル使用メモリ | 184,652 KB |
実行使用メモリ | 220,564 KB |
最終ジャッジ日時 | 2024-10-12 19:31:12 |
合計ジャッジ時間 | 28,826 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
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] 87 | } | ^
ソースコード
#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:resetvoid 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;}