結果
問題 | No.255 Splarrraaay スプラーレェーーイ |
ユーザー |
![]() |
提出日時 | 2020-08-20 15:03:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,272 ms / 10,000 ms |
コード長 | 3,838 bytes |
コンパイル時間 | 2,059 ms |
コンパイル使用メモリ | 140,740 KB |
実行使用メモリ | 96,236 KB |
最終ジャッジ日時 | 2024-10-13 10:33:28 |
合計ジャッジ時間 | 14,968 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
main.cpp:29:20: warning: integer overflow in expression of type 'long long int' results in '-5973893300308410287' [-Woverflow] 29 | const ll INF = mod * mod; | ~~~~^~~~~
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>#include<complex>#include<numeric>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;constexpr ll mod = 1000000000000000009;const ll INF = mod * mod;typedef pair<int, int>P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)#define all(v) (v).begin(),(v).end()typedef pair<ll, ll> LP;typedef double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-12;const ld pi = acos(-1.0);void modadd(ll& a, ll b) {a += b; while (a >= mod)a -= mod;}vector<ll> vx;struct SegT {private:int n; vector<vector<ll>> node; vector<P> lazy; vector<int> lazy2;const vector<ll> init_c = { 0,0,0,0,0 };public:SegT(int sz) {n = 1;while (n < sz)n <<= 1;node.resize(2 * n - 1, init_c);lazy.resize(2 * n - 1, { -1,0 });lazy2.resize(2 * n - 1, 0);}vector<ll> f(vector<ll> a, vector<ll> b) {rep(i, 5)a[i] += b[i]; return a;}P h(P a, P b,int z) {if (a.first != b.first||z==31)return a;else {a.second += b.second; return a;}}void eval(int k, int l, int r) {if (lazy[k].first < 0)return;rep(i, 5)if (lazy2[k] & (1 << i))node[k][i] = 0;node[k][lazy[k].first] += (vx[r] - vx[l]) * lazy[k].second;if (r - l > 1) {lazy[2 * k + 1] = h(lazy[k], lazy[2 * k + 1],lazy2[k]);lazy2[2 * k + 1] |= lazy2[k];lazy[2 * k + 2] = h(lazy[k], lazy[2 * k + 2],lazy2[k]);lazy2[2 * k + 2] |= lazy2[k];}lazy[k] = P{ -1,0 };lazy2[k] = 0;}void add(int x, int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0)r = n;eval(k, l, r);if (r <= a || b <= l)return;if (a <= l && r <= b) {lazy[k] = { x,1 };lazy2[k] |= 31 - (1 << x);eval(k, l, r);}else {add(x, a, b, k * 2 + 1, l, (l + r) / 2);add(x, a, b, k * 2 + 2, (l + r) / 2, r);node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);}}vector<ll> query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0)r = n;eval(k, l, r);if (r <= a || b <= l)return init_c;if (a <= l && r <= b)return node[k];else {vector<ll> vl = query(a, b, k * 2 + 1, l, (l + r) / 2);vector<ll> vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return f(vl, vr);}}};void solve() {ll n; int q; cin >> n >> q;vector<int> t(q);vector<ll> l(q), r(q);rep(i, q) {cin >> t[i] >> l[i] >> r[i];r[i]++;vx.push_back(l[i]);vx.push_back(r[i]);}vx.push_back(0);vx.push_back(n);sort(all(vx));vx.erase(unique(all(vx)), vx.end());rep(i, q) {l[i] = lower_bound(all(vx), l[i]) - vx.begin();r[i] = lower_bound(all(vx), r[i]) - vx.begin();}SegT st(vx.size());vector<ll> score(5, 0);rep(i, q) {if (t[i] == 0) {vector<ll> v = st.query(l[i], r[i]);vector<LP> vs;rep(j, 5)vs.push_back({ v[j],j });sort(all(vs));if (vs[3].first < vs[4].first) {modadd(score[vs[4].second], vs[4].first);}}else {st.add(t[i] - 1, l[i], r[i]);}}vector<ll> v = st.query(0, vx.size() - 1);rep(i, 5) {modadd(score[i], v[i]);}rep(i, 5) {if (i > 0)cout << " ";cout << score[i];}cout << "\n";}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(10);//init_f();//expr();//int t; cin >> t; rep(i, t)//while (cin >> n >> m>>s1>>s2>>t, n)solve();return 0;}