結果
| 問題 | No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ |
| ユーザー |
 anta
|
| 提出日時 | 2015-06-19 22:49:28 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 5,000 ms |
| コード長 | 5,711 bytes |
| コンパイル時間 | 1,020 ms |
| コンパイル使用メモリ | 97,384 KB |
| 実行使用メモリ | 7,768 KB |
| 最終ジャッジ日時 | 2024-07-07 04:09:09 |
| 合計ジャッジ時間 | 2,438 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:200:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
200 | scanf("%d%d%d", &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; }const int K = 3;typedef int Val;struct Sum {int cnt[K];Sum() { rep(k, K) cnt[k] = 0; }Sum(const Val &val, int pos) { rep(k, K) cnt[k] = 0; cnt[val] = 1; }Sum &operator+=(const Sum &that) {rep(k, K) cnt[k] += that.cnt[k];return *this;}Sum operator+(const Sum &that) const { return Sum(*this) += that; }};struct Add {bool a; Val col;Add(): a(false), col(-1) { }explicit Add(Val c): a(true), col(c) { }Add &operator+=(const Add &that) {if(that.a)*this = that;return *this;}void addToVal(Val &val, int pos) const {if(a)val = col;}void addToSum(Sum &sum, int left, int right) const {if(a) {rep(k, K) sum.cnt[k] = 0;sum.cnt[col] = right - left;}}};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() {int N, Q;while(~scanf("%d%d", &N, &Q)) {SegmentTree segt;segt.init(N, Val(0));ll bonusA = 0, bonusB = 0;rep(ii, Q) {int x, l, r;scanf("%d%d%d", &x, &l, &r), ++ r;if(x == 0) {Sum sum = segt.getRangeCommutative(l, r);int A = sum.cnt[1], B = sum.cnt[2];if(A > B)bonusA += A;else if(A < B)bonusB += B;}else if(x == 1) {segt.addToRange(l, r, Add(1));}else if(x == 2) {segt.addToRange(l, r, Add(2));}else abort();}Sum sum = segt.getRangeCommutative(0, N);ll A = bonusA + sum.cnt[1], B = bonusB + sum.cnt[2];cout << A << " " << B << endl;}return 0;}