結果
問題 | No.2716 Falcon Method |
ユーザー | 👑 nu50218 |
提出日時 | 2024-04-05 21:53:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 486 ms / 2,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 3,140 ms |
コンパイル使用メモリ | 222,272 KB |
実行使用メモリ | 9,944 KB |
最終ジャッジ日時 | 2024-04-05 21:54:07 |
合計ジャッジ時間 | 10,619 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 1 ms
6,676 KB |
testcase_05 | AC | 1 ms
6,676 KB |
testcase_06 | AC | 4 ms
6,676 KB |
testcase_07 | AC | 4 ms
6,676 KB |
testcase_08 | AC | 4 ms
6,676 KB |
testcase_09 | AC | 4 ms
6,676 KB |
testcase_10 | AC | 4 ms
6,676 KB |
testcase_11 | AC | 402 ms
9,584 KB |
testcase_12 | AC | 296 ms
9,596 KB |
testcase_13 | AC | 229 ms
9,744 KB |
testcase_14 | AC | 390 ms
8,576 KB |
testcase_15 | AC | 248 ms
9,416 KB |
testcase_16 | AC | 312 ms
8,704 KB |
testcase_17 | AC | 366 ms
8,900 KB |
testcase_18 | AC | 451 ms
9,140 KB |
testcase_19 | AC | 321 ms
8,576 KB |
testcase_20 | AC | 256 ms
9,284 KB |
testcase_21 | AC | 360 ms
8,832 KB |
testcase_22 | AC | 435 ms
9,944 KB |
testcase_23 | AC | 463 ms
9,944 KB |
testcase_24 | AC | 486 ms
9,944 KB |
testcase_25 | AC | 2 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
testcase_27 | AC | 422 ms
9,944 KB |
testcase_28 | AC | 457 ms
9,944 KB |
ソースコード
#ifdef LOCAL #include <local.hpp> #else #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2") #include <bits/stdc++.h> #define debug(...) ((void)0) #define postprocess(...) ((void)0) #endif #include <atcoder/fenwicktree.hpp> using namespace std; using ll = long long; using ld = long double; void solve([[maybe_unused]] int test) { int N, Q; cin >> N >> Q; string S; cin >> S; atcoder::fenwick_tree<ll> fwt_x(2 * N), fwt_y(2 * N); for (int i = 0; i < N; i++) { if (S[i] == 'D') { fwt_x.add(i, 1); fwt_x.add(i + N, 1); } else { fwt_y.add(i, 1); fwt_y.add(i + N, 1); } } for (int q = 0; q < Q; q++) { ll H, W, P; cin >> H >> W >> P; ll imin = 0; ll imax = H + W; while (imax - imin > 1) { ll imid = (imin + imax) / 2; ll loop = imid / N; pair<ll, ll> cur = { loop * fwt_x.sum(0, N), loop * fwt_y.sum(0, N), }; cur.first += fwt_x.sum(P, P + imid % N); cur.second += fwt_y.sum(P, P + imid % N); if (cur.first >= H || cur.second >= W) { imax = imid; } else { imin = imid; } } cout << (P + imax) % N << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(i); } postprocess(); }