結果

問題 No.255 Splarrraaay スプラーレェーーイ
ユーザー FF256grhyFF256grhy
提出日時 2017-07-20 02:49:04
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,537 ms / 10,000 ms
コード長 3,841 bytes
コンパイル時間 1,928 ms
コンパイル使用メモリ 182,552 KB
実行使用メモリ 32,656 KB
最終ジャッジ日時 2024-10-08 14:45:41
合計ジャッジ時間 16,906 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(int i = (l) ; i < (r); i++)
#define incII(i, l, r) for(int i = (l) ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r) ; i >= (l); i--)
#define inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) < (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define FOR(it, v) for(auto it = v.begin(); it != v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)
template<typename T> bool setmin(T & a, T b) { if(b < a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax(T & a, T b) { if(b > a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
// ---- ----
const LL Q = 150000;
LL n, q, x[Q], l[Q], r[Q];
vector<LL> v;
map<LL, LL> id;
const LL C = 601;
const LL N = 500;
LL cn[C]; // full
pair<LL, LL> f[C];
pair<LL, LL> p[C][N];
LL ps[C][6]; // part
LL ans[6], MOD = 1000000000000000009LL;
LL val(LL i) {
return (i < v.size() ? v[i] : v.back());
}
void fall(LL i) {
if(cn[i] == 0) { return; }
inc(j, N) {
p[i][j] = MP(f[i].FI, f[i].SE + (cn[i] == 1 && p[i][j].FI == f[i].FI ? p[i][j].SE : 0));
}
inc1(j, 5) { ps[i][j] = 0; }
inc(j, N) { ps[i][p[i][j].FI] += p[i][j].SE * (val(i * N + j + 1) - val(i * N + j)); }
cn[i] = 0;
f[i] = MP(0, 0);
}
void count() {
inc(i, C) { fall(i); }
inc(i, C) {
inc1(j, 5) {
(ans[j] += ps[i][j]) %= MOD;
}
}
}
void solve(LL x, LL l, LL r) {
LL sum[6];
inc1(i, 5) { sum[i] = 0; }
inc(i, C) {
LL il = i * N;
LL ir = (i + 1) * N;
if(ir <= l || r <= il) { continue; }
if(l <= il && ir <= r) { // full
if(x == 0) {
sum[f[i].FI] += f[i].SE * (val(ir) - val(il));
if(cn[i] == 1) { sum[f[i].FI] += ps[i][f[i].FI]; }
if(cn[i] == 0) { inc1(j, 5) { sum[j] += ps[i][j]; } }
} else {
if(f[i].FI == x) { f[i].SE++; } else { f[i] = MP(x, 1); cn[i]++; }
}
} else { // part
if(x != 0) { fall(i); }
LL b = max(l, il);
LL e = min(r, ir);
assert(b < e);
incID(jj, b, e) {
LL j = jj % N;
LL w = val(jj + 1) - val(jj);
if(x == 0) {
sum[f[i].FI] += f[i].SE * w;
sum[p[i][j].FI] += (cn[i] == 0 || (cn[i] == 1 && p[i][j].FI == f[i].FI) ? p[i][j].SE * w : 0);
} else {
if(p[i][j].FI != x) { ps[i][p[i][j].FI] -= p[i][j].SE * w; p[i][j].SE = 0; }
p[i][j].FI = x;
p[i][j].SE++;
ps[i][x] += w;
}
}
}
}
if(x == 0) {
vector<pair<LL, LL>> vp;
inc1(i, 5) { vp.EB(sum[i], i); assert(sum[i] <= 1.5e18); }
sort(RALL(vp));
if(vp[0].FI != vp[1].FI) { (ans[vp[0].SE] += vp[0].FI) %= MOD; }
}
}
int main() {
cin >> n >> q;
inc(i, q) { cin >> x[i] >> l[i] >> r[i]; r[i]++; }
inc(i, q) {
v.PB(l[i]);
v.PB(r[i]);
}
sort(ALL(v));
v.erase(unique(ALL(v)), v.end());
inc(i, v.size()) { id[v[i]] = i; }
inc(i, q) { solve(x[i], id[l[i]], id[r[i]]); }
count();
inc1(i, 5) { cout << (i == 1 ? "" : " ") << ans[i]; } cout << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0