結果
問題 | No.151 セグメントフィッシング |
ユーザー | rantd |
提出日時 | 2015-02-25 22:41:57 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 11 ms / 5,000 ms |
コード長 | 3,117 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 168,064 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-23 23:27:00 |
合計ジャッジ時間 | 3,270 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,948 KB |
testcase_08 | AC | 3 ms
6,944 KB |
testcase_09 | AC | 4 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 9 ms
6,944 KB |
testcase_13 | AC | 9 ms
6,940 KB |
testcase_14 | AC | 9 ms
6,944 KB |
testcase_15 | AC | 9 ms
6,940 KB |
testcase_16 | AC | 9 ms
6,944 KB |
testcase_17 | AC | 7 ms
6,944 KB |
testcase_18 | AC | 7 ms
6,940 KB |
testcase_19 | AC | 11 ms
6,940 KB |
testcase_20 | AC | 11 ms
6,940 KB |
testcase_21 | AC | 8 ms
6,940 KB |
testcase_22 | AC | 8 ms
6,940 KB |
testcase_23 | AC | 7 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define repu(i, begin, end) for (__typeof(begin) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define repe(i, begin, end) for (__typeof(begin) i = (begin); i != (end) + 1 - 2 * ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define mem(a, x) memset(a, x, sizeof(a)) #define all(a) a.begin(), a.end() #define count_bits(x) __builtin_popcount(x) #define count_bitsll(x) __builtin_popcountll(x) #define least_bits(x) __builtin_ffs(x) #define least_bitsll(x) __builtin_ffsll(x) #define most_bits(x) 32 - __builtin_clz(x) #define most_bitsll(x) 64 - __builtin_clz(x) vector<string> split(const string &s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(x); return v; } #define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); } void err(vector<string>::iterator it) {} template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n'; err(++it, args...); } typedef long long ll; const int MOD = 1000000007; template<class T> inline T tmin(T a, T b) {return (a < b) ? a : b;} template<class T> inline T tmax(T a, T b) {return (a > b) ? a : b;} template<class T> inline void amax(T &a, T b) {if (b > a) a = b;} template<class T> inline void amin(T &a, T b) {if (b < a) a = b;} template<class T> inline T tabs(T a) {return (a > 0) ? a : -a;} template<class T> T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;} template<class T> struct Fenwick { vector<T> bit; int fw_size; Fenwick(int _n) { fw_size = _n; bit.assign(_n + 1, 0); } void add(int ind, T val) { for (int i = ind; i <= fw_size; i += i & -i) { bit[i] += val; } } T get(int ind) { T ans = 0; for (int i = ind; i > 0; i -= i & -i) { ans += bit[i]; } return ans; } }; void amod(int &x, int mod) { x %= mod; if (x < 0) x += mod; } int main(int argc, char *argv[]) { ios_base::sync_with_stdio(false); int N, Q, y, z, pos; char x; cin >> N >> Q; int M = N + N; Fenwick<ll> fw = Fenwick<ll>(M); repe(t, 1, Q) { cin >> x >> y >> z; if (x == 'R') { pos = y - t; amod(pos, M); fw.add(pos + 1, z); } if (x == 'L') { pos = M - y - 1 - t; amod(pos, M); fw.add(pos + 1, z); } if (x == 'C') { ll ans = 0; // right int posl = y - t, posr = z - 1 - t; amod(posl, M); amod(posr, M); if (posl <= posr) ans += fw.get(posr + 1) - fw.get(posl); else ans += fw.get(M) - fw.get(posl) + fw.get(posr + 1); // left posr = M - 1 - y - t, posl = M - z - t; amod(posl, M); amod(posr, M); if (posl <= posr) ans += fw.get(posr + 1) - fw.get(posl); else ans += fw.get(M) - fw.get(posl) + fw.get(posr + 1); printf("%lld\n", ans); } } return 0; }