結果
問題 | No.255 Splarrraaay スプラーレェーーイ |
ユーザー |
![]() |
提出日時 | 2015-07-24 23:37:49 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 694 ms / 10,000 ms |
コード長 | 8,104 bytes |
コンパイル時間 | 1,506 ms |
コンパイル使用メモリ | 109,092 KB |
実行使用メモリ | 63,108 KB |
最終ジャッジ日時 | 2024-10-12 19:24:09 |
合計ジャッジ時間 | 8,823 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:244:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 244 | scanf("%d%lld%lld", &x, &l, &r), ++ r; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <string>#include <vector>#include <algorithm>#include <numeric>#include <set>#include <map>#include <queue>#include <iostream>#include <sstream>#include <cstdio>#include <cmath>#include <ctime>#include <cstring>#include <cctype>#include <cassert>#include <limits>#include <functional>#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))#if defined(_MSC_VER) || __cplusplus > 199711L#define aut(r,v) auto r = (v)#else#define aut(r,v) __typeof(v) r = (v)#endif#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)#define all(o) (o).begin(), (o).end()#define pb(x) push_back(x)#define mp(x,y) make_pair((x),(y))#define mset(m,v) memset(m,v,sizeof(m))#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLusing namespace std;typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }struct ModInt {static const ll Mod;long long x;ModInt(): x(0) { }ModInt(signed sig) { ll sigt = sig % Mod; if(sigt < 0) sigt += Mod; x = sigt; }ModInt(signed long long sig) { ll sigt = sig % Mod; if(sigt < 0) sigt += Mod; x = sigt; }ll get() const { return x; }ModInt &operator+=(ModInt that) { if((x += that.x) >= Mod) x -= Mod; return *this; }ModInt operator+(ModInt that) const { return ModInt(*this) += that; }};const ll ModInt::Mod = (ll)1e18+9;typedef ModInt mint;const int K = 5;struct Val {int team, val;ll size;Val(): team(0), val(0), size(0) { }Val(int t, int v, ll s): team(t), val(v), size(s) { }};struct Sum {ll sums[K];ll size;Sum() { rep(k, K) sums[k] = 0; size = 0; }Sum(const Val &val, int pos) {rep(k, K) sums[k] = 0;sums[val.team] = (ll)val.val * val.size;size = val.size;}Sum &operator+=(const Sum &that) {rep(k, K) sums[k] += that.sums[k];size += that.size;return *this;}Sum operator+(const Sum &that) const { return Sum(*this) += that; }};struct Add {bool a; bool clr; Val x;Add(): a(false), clr(false), x() { }explicit Add(Val c): a(true), clr(false), x(c) { }Add &operator+=(const Add &that) {if(that.a) {if(!a) {*this = that;}else if(x.team == that.x.team && !that.clr) {// clr = clr;x.val += that.x.val;}else {clr = true;x = that.x;}}return *this;}void addToVal(Val &val, int pos) const {if(a) {if(clr) val.val = 0;if(val.team == x.team) {val.val += x.val;}else {val.team = x.team;val.val = x.val;}}}void addToSum(Sum &sum, int left, int right) const {if(a) {rep(k, K) if(k != x.team) sum.sums[k] = 0;if(clr) sum.sums[x.team] = 0;sum.sums[x.team] += (ll)sum.size * x.val;}}};struct SegmentTree {vector<Val> leafs;vector<Sum> nodes;vector<Add> add;vector<int> leftpos, rightpos;int n, n2;void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }void init(const vector<Val> &u) {n = 1; while(n < (int)u.size()) n *= 2;n2 = (n - 1) / 2 + 1;leafs = u; leafs.resize(n, Val());nodes.resize(n);for(int i = n-1; i >= n2; -- i)nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n);for(int i = n2-1; i > 0; -- i)nodes[i] = nodes[i*2] + nodes[i*2+1];add.assign(n, Add());leftpos.resize(n); rightpos.resize(n);for(int i = n-1; i >= n2; -- i) {leftpos[i] = i*2-n;rightpos[i] = (i*2+1-n) + 1;}for(int i = n2-1; i > 0; -- i) {leftpos[i] = leftpos[i*2];rightpos[i] = rightpos[i*2+1];}}Val get(int i) {int indices[128];int k = getIndices(indices, i, i+1);propagateRange(indices, k);return leafs[i];}Sum getRangeCommutative(int i, int j) {int indices[128];int k = getIndices(indices, i, j);propagateRange(indices, k);Sum res = Sum();for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {if(l & 1) res += sum(l ++);if(r & 1) res += sum(-- r);}return res;}Sum getRange(int i, int j) {int indices[128];int k = getIndices(indices, i, j);propagateRange(indices, k);Sum res = Sum();for(; i && i + (i&-i) <= j; i += i&-i)res += sum((n+i) / (i&-i));for(k = 0; i < j; j -= j&-j)indices[k ++] = (n+j) / (j&-j) - 1;while(-- k >= 0) res += sum(indices[k]);return res;}void set(int i, const Val &x) {int indices[128];int k = getIndices(indices, i, i+1);propagateRange(indices, k);leafs[i] = x;mergeRange(indices, k);}void addToRange(int i, int j, const Add &x) {if(i >= j) return;int indices[128];int k = getIndices(indices, i, j);propagateRange(indices, k);int l = i + n, r = j + n;if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {if(l & 1) add[l ++] += x;if(r & 1) add[-- r] += x;}mergeRange(indices, k);}private:int getIndices(int indices[], int i, int j) const {int k = 0, l, r;if(i >= j) return 0;for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {indices[k ++] = l;indices[k ++] = r;}for(; l; l >>= 1) indices[k ++] = l;return k;}void propagateRange(int indices[], int k) {for(int i = k - 1; i >= 0; -- i)propagate(indices[i]);}void mergeRange(int indices[], int k) {for(int i = 0; i < k; ++ i)merge(indices[i]);}inline void propagate(int i) {if(i >= n) return;add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);if(i * 2 < n) {add[i * 2] += add[i];add[i * 2 + 1] += add[i];}else {add[i].addToVal(leafs[i * 2 - n], i * 2 - n);add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);}add[i] = Add();}inline void merge(int i) {if(i >= n) return;nodes[i] = sum(i * 2) + sum(i * 2 + 1);}inline Sum sum(int i) {propagate(i);return i < n ? nodes[i] : Sum(leafs[i - n], i - n);}};int main() {ll N; int Q;while(cin >> N >> Q) {typedef pair<ll,ll> pll;vector<pair<int,pll> > queries(Q);vector<ll> values;rep(ii, Q) {int x; ll l, r;// x=rand()%6,l=rand()%N,r=rand()%N;if(l>r)swap(l,r);++r;scanf("%d%lld%lld", &x, &l, &r), ++ r;queries[ii] = mp(x, mp(l, r));values.push_back(l);values.push_back(r);}sort(all(values)); values.erase(unique(all(values)), values.end());int X = values.size();SegmentTree segt;vector<Val> initval(X);rep(i, X-1) initval[i] = Val(0, 0, values[i+1] - values[i]);segt.init(initval);mint pts[K] = {};// vector<Val> naiveval((int)N);rep(ii, Q) {int x = queries[ii].first;ll L = queries[ii].second.first;ll R = queries[ii].second.second;int l = lower_bound(all(values), L) - values.begin();int r = lower_bound(all(values), R) - values.begin();;if(x == 0) {Sum sum = segt.getRangeCommutative(l, r);int k = max_element(sum.sums, sum.sums + K) - sum.sums;if(count(sum.sums, sum.sums + K, sum.sums[k]) == 1)pts[k] += sum.sums[k];// ll naivesum[K]={};// reu(i,(int)L,(int)R)naivesum[naiveval[i].team]+=naiveval[i].val;// rep(i,K)if(sum.sums[i]!=naivesum[i])// cerr<<sum.sums[i]<<" != "<<naivesum[i]<<endl;}else if(x <= 5) {segt.addToRange(l, r, Add(Val(x-1, 1, 0)));// reu(i, (int)L, (int)R)// Add(Val(x-1, 1, 0)).addToVal(naiveval[i], -1);}else return 0;// Sum sum = segt.getRangeCommutative(0, X);// rep(l, K) cerr << sum.sums[l] << ", "; cerr << endl;// ll naivesum[K]={};// reu(i,0,(int)N)naivesum[naiveval[i].team]+=naiveval[i].val;// rep(i,K)if(sum.sums[i]!=naivesum[i])// cerr<<sum.sums[i]<<" != "<<naivesum[i]<<endl;}Sum sum = segt.getRangeCommutative(0, X);rep(k, K)pts[k] += sum.sums[k];cout << pts[0].get() << " " << pts[1].get() << " " << pts[2].get() << " " << pts[3].get() << " " << pts[4].get() << endl;break;}return 0;}