結果
問題 | No.259 セグメントフィッシング+ |
ユーザー | 👑 CleyL |
提出日時 | 2023-05-30 13:44:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 3,276 bytes |
コンパイル時間 | 1,086 ms |
コンパイル使用メモリ | 81,028 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-06-08 20:08:17 |
合計ジャッジ時間 | 6,737 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 187 ms
19,544 KB |
testcase_09 | AC | 186 ms
19,576 KB |
testcase_10 | AC | 194 ms
19,712 KB |
testcase_11 | AC | 192 ms
19,708 KB |
testcase_12 | AC | 189 ms
19,700 KB |
testcase_13 | AC | 200 ms
19,584 KB |
testcase_14 | AC | 199 ms
19,712 KB |
testcase_15 | AC | 206 ms
19,584 KB |
testcase_16 | AC | 202 ms
19,456 KB |
testcase_17 | AC | 200 ms
19,712 KB |
testcase_18 | AC | 207 ms
19,584 KB |
testcase_19 | AC | 205 ms
19,584 KB |
testcase_20 | AC | 203 ms
19,456 KB |
testcase_21 | AC | 204 ms
19,712 KB |
testcase_22 | AC | 202 ms
19,612 KB |
testcase_23 | AC | 82 ms
5,376 KB |
testcase_24 | AC | 119 ms
19,640 KB |
testcase_25 | AC | 116 ms
19,544 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; template< typename T, typename F> struct SegmentTree{ private: int n; vector<T> node; F f; T initer; public: SegmentTree(int n_, F f, T initer) : f(f),initer(initer) { n = 1; while(n < n_)n*=2; node.resize(2*n-1, initer); } SegmentTree(int n_, F f,T initer, vector<T> x) : f(f),initer(initer) { n = 1; while(n < n_)n*=2; node.resize(2*n-1, initer); set(x); } void set(vector<T> x){ for(int i = 0; n > i; i++){ update(i,x[i]); } } void update(int x, T val){ x += (n-1); node[x] = val; while(x > 0){ x = (x-1)/2; node[x] = f(node[2*x+1],node[2*x+2]); } } void add(int x, T val){ x += (n-1); node[x] += val; while(x > 0){ x = (x-1)/2; node[x] = f(node[2*x+1],node[2*x+2]); } } T getf(int a,int b, int k=0, int l=0, int r=-1){ if(r < 0){ r = n-1; } if(r < a || b < l){ return initer; } if(a <= l && r <= b){ return node[k]; } T vl = getf(a,b,2*k+1,l,(l+r)/2); T vr = getf(a,b,2*k+2,(l+r)/2+1,r); return f(vl,vr); } }; template <typename T, typename F> SegmentTree<T, F> get_segment_tree(int N, const F &f, T initer){ return SegmentTree<T,F>{N,f,initer}; } template <typename T, typename F> SegmentTree<T, F> get_segment_tree(int N, const F &f, T initer, vector<T> x){ return SegmentTree<T,F>{N,f,initer,x}; } int main(){ int n,q;cin>>n>>q; auto l = get_segment_tree(n*2, [](long long a, long long b){return a+b;}, 0LL); auto r = get_segment_tree(n*2, [](long long a, long long b){return a+b;}, 0LL); for(int i = 0; q > i; i++){ string s;cin>>s; if(s == "L"){ long long t,y,z;cin>>t>>y>>z; int nwi = (y+t)%(n*2); //cout << nwi << endl; l.add(nwi,z); }else if(s == "R"){ long long t,y,z;cin>>t>>y>>z; int nwi = ((y-t)%(n*2)+(n*2))%(n*2); //cout << nwi << endl; r.add(nwi, z); }else{ long long t; int y,z;cin>>t>>y>>z;z--; //l pair<int,int> lf = {(y+t)%(n*2), (z+t)%(n*2)}; long long ans = 0; if(lf.first <= lf.second){ ans += l.getf(lf.first, lf.second); }else{ ans += l.getf(lf.first, 2*n-1); ans += l.getf(0, lf.second); } pair<int,int> ls = {((n+t-1-z)+n)%(n*2), ((n+t-1-y)+n)%(n*2)}; if(ls.first <= ls.second){ ans += l.getf(ls.first, ls.second); }else{ ans += l.getf(ls.first, 2*n-1); ans += l.getf(0, ls.second); } pair<int,int> rf = {(((y-t)%(n*2))+(n*2))%(n*2), (((z-t)%(n*2))+(n*2))%(n*2)}; if(rf.first <= rf.second){ ans += r.getf(rf.first, rf.second); }else{ ans += r.getf(rf.first, 2*n-1); ans += r.getf(0, rf.second); } pair<int,int> rs = {((((n-t-1-z)+n)%(n*2)) + (n*2))%(n*2), ((((n-t-1-y)+n)%(n*2))+(n*2))%(n*2)}; if(rs.first <= rs.second){ ans += r.getf(rs.first, rs.second); }else{ ans += r.getf(rs.first, 2*n-1); ans += r.getf(0, rs.second); } cout << ans << endl; } } }