結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | tone |
提出日時 | 2019-07-29 13:46:45 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,232 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 131,852 KB |
実行使用メモリ | 7,652 KB |
最終ジャッジ日時 | 2024-11-30 14:26:01 |
合計ジャッジ時間 | 6,354 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 86 ms
7,528 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
ソースコード
#include <iostream> #include <string> #include <vector> #include <deque> #include <queue> #include <algorithm> #include <bitset> #include <tuple> #include <set> #include <map> #define range(i, r) for(int i=0;i<r;i++) #define ranges(i, l, r) for(int i=l;i<r;i++) #define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c)) #define vvi std::vector<std::vector<int> > #define vvl std::vector<std::vector<ll> > #define MODs 1000000007; #define MODn 1000000009; typedef long long int ll; using namespace std; //------------------------------------------------------------------- int M=1; std::vector<int> segA, segB, segsumA, segsumB; void init(int N){ while(M<N) M*=2; M=M*2-1; for(int i=0;i<M;i++) { segA.push_back(0); segsumA.push_back(0); segB.push_back(0); segsumB.push_back(0); } } ll su(int a, int b, int l, int r, int k, int m){ if(r<=a||b<=l) return 0; else if(a<=l&&r<=b) return (m==1?segA[k]:segB[k])*(r-l)+(m==1?segsumA[k]:segsumB[k]); else{ ll res = (min(b, r)-max(a, l))*(m==1?segA[k]:segB[k]); res+=su(a, b, l, (l+r)/2, k*2+1, m); res+=su(a, b, (l+r)/2, r, k*2+2, m); return res; } } void ad(int a, int b, int l, int r, int x, int k, int m){ if(a<=l&&r<=b) { (m==1?segA[k]:segB[k])+=x; (m==1?segsumB[k]:segsumA[k])-=su(a, b, 0, (M+1)/2, 0, (m==1?2:1)); }else if(l<b&&a<r){ (m==1?segsumA[k]:segsumB[k])+=(min(b,r)-max(a, l))*x; (m==1?segsumB[k]:segsumA[k])-=su(a, b, 0, (M+1)/2, 0,(m==1?2:1)); ad(a, b, l, (l+r)/2, x, k*2+1, m); ad(a, b, (l+r)/2, r, x, k*2+2, m); } } //------------------------------------------------------------------- int main(int argc, char const *argv[]) { int N, Q, x, l, r; ll score_a=0, score_b=0; std::cin >> N; std::cin >> Q; init(N); for(int i=0;i<Q;i++) { std::cin >> x >> l >> r; if(x==0){ ll bonus_a=su(l, r+1, 0, (M+1)/2, 0, 1); ll bonus_b=su(l, r+1, 0, (M+1)/2, 0, 2); if(bonus_a>bonus_b) score_a+=bonus_a; else if(bonus_b>bonus_a) score_b+=bonus_b; }else{ ad(l, r+1, 0, (M+1)/2, 1, 0, x); } } score_a+=su(0, (M+1)/2, 0, (M+1)/2, 0, 1); score_b+=su(0, (M+1)/2, 0, (M+1)/2, 0, 2); std::cout << score_a << " " << score_b << '\n'; return 0; }