結果
問題 | No.255 Splarrraaay スプラーレェーーイ |
ユーザー |
![]() |
提出日時 | 2016-07-19 09:31:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 376 ms / 10,000 ms |
コード長 | 4,912 bytes |
コンパイル時間 | 1,977 ms |
コンパイル使用メモリ | 104,996 KB |
実行使用メモリ | 46,848 KB |
最終ジャッジ日時 | 2024-10-15 17:17:27 |
合計ジャッジ時間 | 6,971 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC target ("avx")// #pragma GCC target ("sse4") // SPOJ, codechef#include <cstdio>#include <cassert>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <map>#include <set>#include <functional>#include <tuple>#define _rep(_1, _2, _3, _4, name, ...) name#define rep2(i, n) rep3(i, 0, n)#define rep3(i, a, b) rep4(i, a, b, 1)#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)using namespace std;using i64 = long long;using u8 = unsigned char;using u32 = unsigned;using u64 = unsigned long long;using f80 = long double;const i64 mod = i64(1e18) + 9;const int C = 5;using Col = i64[C];struct SegmentTree {struct Node {Col cnts;int color;int width;i64 len;bool color_changed;};using elem = Node;SegmentTree(int n) : size_(n) {tree = new elem[2 * size_];}~SegmentTree() { delete [] tree; }void build(i64* X) {for (int i = 0; i < size_; ++i) {tree[size_ + i] = {{}, -1, 0, X[i + 1] - X[i], false};}for (int i = size_ - 1; i >= 0; --i) {tree[i] = {{}, -1, 0, 0, false};tree[i].len = tree[2 * i].len + tree[2 * i + 1].len;}}void colorize(int k, int col, int width, bool color_changed=false) {rep(i, C) if (i != col) tree[k].cnts[i] = 0;int& tc = tree[k].color;bool& tcc = tree[k].color_changed;if (tc == col && !color_changed) {tree[k].width += width;} else {if (color_changed) tree[k].cnts[col] = 0;tree[k].width = width;}tcc |= color_changed || (tc >= 0 && col != tc);tc = col;}void propagate(int k) {int ks[30], ki = 0;for (k >>= 1; k >= 1; k >>= 1) ks[ki++] = k;for (; ki; ) {int k = ks[--ki];int c = tree[k].color;bool cc = tree[k].color_changed;if (c >= 0) {int w = tree[k].width;tree[k].cnts[c] += tree[k].len * w;colorize(2 * k + 0, c, w, cc);colorize(2 * k + 1, c, w, cc);tree[k].color = -1;tree[k].color_changed = false;}}}inline void cadd(Col cnts, int k) {rep(i, C) cnts[i] += tree[k].cnts[i];int c = tree[k].color;if (c >= 0) cnts[c] += tree[k].width * tree[k].len;}inline void fix(int k) {assert(tree[k].color == -1);auto* cnts = tree[k].cnts;rep(i, C) cnts[i] = 0;;cadd(cnts, 2 * k + 0);cadd(cnts, 2 * k + 1);}void update(int l, int r, int col) {l += size_; r += size_;propagate(l); propagate(r - 1);bool lup = false, rup = false;for (; l < r; l >>= 1, r >>= 1) {if (lup) fix(l - 1);if (rup) fix(r);if (l & 1) colorize(l++, col, 1), lup = true;if (r & 1) colorize(--r, col, 1), rup = true;}for (--l; l < r; l >>= 1, r >>= 1) {if (lup) fix(l);if (rup) fix(r);}for (; l; l >>= 1) fix(l);}void query(int l, int r, Col cnts) {rep(i, C) cnts[i] = 0;l += size_; r += size_;propagate(l); propagate(r - 1);for (; l < r; l >>= 1, r >>= 1) {if (l & 1) cadd(cnts, l++);if (r & 1) cadd(cnts, --r);}}int size_;elem* tree;};#define getchar getchar_unlockedi64 get_i64() {i64 n, c;while ((c = getchar()) < '0') if (c == EOF) return -1;n = c - '0';while ((c = getchar()) >= '0') n = n * 10 + c - '0';return n;}const i64 Q_MAX = 150000;struct {int c;i64 x, y;} qs[Q_MAX];i64 xs[Q_MAX * 2];void solve() {i64 N;while (~(N = get_i64())) {int Q = get_i64();rep(i, Q) {int c = get_i64() - 1;i64 x = get_i64();i64 y = get_i64() + 1;qs[i] = {c, x, y};xs[2 * i] = x;xs[2 * i + 1] = y;}int size = 2 * Q;sort(xs, xs + size);size = unique(xs, xs + size) - xs;auto tree = SegmentTree(max(0, size - 1));tree.build(xs);Col cnts;Col ans = {};rep(i, Q) {int c = qs[i].c;int x = lower_bound(xs, xs + size, qs[i].x) - xs;int y = lower_bound(xs + x, xs + size, qs[i].y) - xs;if (c < 0) {tree.query(x, y, cnts);i64 mx = 0;int id = -1;rep(i, C) {if (cnts[i] > mx) {mx = cnts[i];id = i;} else if (cnts[i] == mx) {id = -1;}}if (id >= 0) ans[id] = (ans[id] + cnts[id]) % mod;} else {tree.update(x, y, c);}}tree.query(0, size - 1, cnts);rep(i, C) ans[i] = (ans[i] + cnts[i]) % mod;printf("%lld", ans[0]);rep(i, 1, C) printf(" %lld", ans[i]);puts("");}}int main() {clock_t beg = clock();solve();clock_t end = clock();fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);return 0;}