結果
問題 | No.255 Splarrraaay スプラーレェーーイ |
ユーザー |
![]() |
提出日時 | 2015-07-25 00:56:31 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,156 ms / 10,000 ms |
コード長 | 4,106 bytes |
コンパイル時間 | 1,372 ms |
コンパイル使用メモリ | 112,932 KB |
実行使用メモリ | 226,124 KB |
最終ジャッジ日時 | 2024-10-12 19:25:23 |
合計ジャッジ時間 | 13,208 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:174:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘__int128*’ [-Wformat=] 174 | scanf("%lld", &n); | ~~~^ ~~ | | | | | __int128* | long long int* main.cpp:174:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 174 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~ main.cpp:176:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 176 | scanf("%d", &qq); | ~~~~~^~~~~~~~~~~ main.cpp: In constructor ‘st::st()’: main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | scanf("%d%lld%lld", &ty, &ll, &rr); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>#include<unordered_map>#include<stdint.h>#include<quadmath.h>using namespace std;#define MAX 200002__int128 n;vector<__int128> v;__int128 MOD = 1000000000000000009LL;struct st{int ty;__int128 l;__int128 r;st(){long long int ll, rr;scanf("%d%lld%lld", &ty, &ll, &rr);l = ll;r = rr;}};vector<st> vv;struct s{__int128 area = 0;int col = -1;__int128 l = -1;__int128 r = -1;__int128 ar[5];__int128 add = 0;bool flag = false;int ge = -1;s(){for (int i = 0; i < 5; i++){ar[i] = 0;}}};#define MAXX 300012s seg[MAXX * 4];void cflag(int b, int x, __int128 k){if (seg[b].col != x){seg[b].col = x;seg[b].add = 0;}seg[b].add += k;if (seg[b].ge!=-1&&seg[b].ge != x){seg[b].flag = true;}}void init(int b, int l, int r){seg[b].l = l;seg[b].r = r;seg[b].area = v[r] - v[l];if (l + 1 == r){return;}init(b * 2 + 1, l, (l + r) >> 1);init(b * 2 + 2, (l + r) >> 1, r);}void chang(int b, int x){seg[b].ge = x;for (int i = 0; i < 5; i++){if (i == x){seg[b].ar[i] += seg[b].area*seg[b].add;}else{seg[b].ar[i] = 0;}}if (seg[b].l + 1 != seg[b].r){cflag(b * 2 + 1, x, seg[b].add);cflag(b * 2 + 2, x, seg[b].add);}seg[b].col = -1;seg[b].add = 0;}void update(int b){if (seg[b].flag){seg[b].ge = -1;for (int i = 0; i < 5; i++){seg[b].ar[i] = 0;}if (seg[b].l + 1 < seg[b].r){seg[b * 2 + 1].add = 0;seg[b * 2 + 2].add = 0;seg[b * 2 + 1].flag = true;seg[b * 2 + 2].flag = true;}}if (seg[b].col == -1){return;}seg[b].flag = false;chang(b, seg[b].col);seg[b].col = -1;return;}inline void add(int b, int l, int r, int ll, int rr, int x){update(b);if (rr <= l || r <= ll){return;}if (ll <= l&&r <= rr){cflag(b, x,1LL);update(b);return;}add(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);add(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);seg[b].ge = -1;for (int i = 0; i < 5; i++){seg[b].ar[i] = seg[b * 2 + 1].ar[i] + seg[b * 2 + 2].ar[i];}update(b);}__int128 sum[5];inline void q(int b, int l, int r, int ll, int rr){update(b);if (rr <= l || r <= ll){return;}if (ll <= l&&r <= rr){for (int i = 0; i < 5; i++){sum[i] += seg[b].ar[i];}return;}q(b * 2 + 1, l, (l + r) >> 1, ll, rr);q(b * 2 + 2, (l + r) >> 1, r, ll, rr);}__int128 b[5];void output(){for (int i = 0; i < 5; i++){sum[i] = 0;}q(0, 0, v.size() - 1, 0, v.size() - 1);for (int i = 0; i < 5; i++){if (i){printf(" ");}__int128 ans = sum[i] + b[i];ans %= MOD;unsigned long long int outt = ans;printf("%lld", outt);}puts("");}int main(){scanf("%lld", &n);int qq;scanf("%d", &qq);for (int i = 0; i < qq; i++){vv.push_back(st());v.push_back(vv.back().l);v.push_back(vv.back().r + 1LL);}v.push_back(n);v.push_back(0);sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());init(0, 0, v.size() - 1);for (int i = 0; i < qq; i++){int ind = lower_bound(v.begin(), v.end(), vv[i].l) - v.begin();int ind2 = lower_bound(v.begin(), v.end(), vv[i].r + 1LL) - v.begin();if (vv[i].ty == 0){for (int i = 0; i < 5; i++){sum[i] = 0;}q(0, 0, v.size() - 1, ind, ind2);int ind = 0;__int128 val = -1LL;for (int i = 0; i < 5; i++){if (val < sum[i]){val = sum[i];ind = i;}}int countt = 0;for (int i = 0; i < 5; i++){if (val == sum[i]){countt++;}}if (countt == 1){b[ind] += val;}if (countt == 0){return 1;}}else{add(0, 0, v.size() - 1, ind, ind2, vv[i].ty - 1);}//output();}output();return 0;}