結果

問題 No.255 Splarrraaay スプラーレェーーイ
ユーザー pekempeypekempey
提出日時 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 | }
      | ^

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0