結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 2024-04-05 22:38:24 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 1,084 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 30,848 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-10-01 02:47:11 |
合計ジャッジ時間 | 3,213 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<stdio.h>char s[200005];long long int x[400005], y[400005];int main(){long long int n, q;scanf("%lld %lld", &n, &q);scanf("%s", s);long long int i;x[0] = y[0] = 0;for (i = 0; i < n; i++){x[i + 1] = x[i];y[i + 1] = y[i];if (s[i] == 'D')x[i + 1]++;elsey[i + 1]++;}for (i = 0; i < n; i++){x[i + 1 + n] = x[i + n];y[i + 1 + n] = y[i + n];if (s[i] == 'D')x[i + 1 + n]++;elsey[i + 1 + n]++;}long long int min, mid, max;long long int h, w, p;long long int f1, f2, f;for (i = 0; i < q; i++){scanf("%lld %lld %lld", &h, &w, &p);if (x[n] > 0)f1 = (h - 1) / x[n];elsef1 = 1e18;if (y[n] > 0)f2 = (w - 1) / y[n];elsef2 = 1e18;if (f1 < f2)f = f1;elsef = f2;h -= x[n] * f;w -= y[n] * f;if (h > x[n] && w > y[n]){h -= x[n];w -= y[n];}min = p;max = 2 * n;while (max - min > 1){mid = (max + min) / 2;if (x[mid] - x[p] < h && y[mid] - y[p] < w)min = mid;elsemax = mid;}printf("%lld\n", max % n);}return 0;}