結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 2024-04-05 21:41:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 2,000 ms |
コード長 | 1,142 bytes |
コンパイル時間 | 3,866 ms |
コンパイル使用メモリ | 260,872 KB |
実行使用メモリ | 6,784 KB |
最終ジャッジ日時 | 2024-10-01 01:56:14 |
合計ジャッジ時間 | 8,932 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int N,Q; cin>>N>>Q; string S; cin>>S; vector<long long> s0(N+1),s1(N+1); for(int i=1;i<=N;i++){ if(S[i-1]=='D')s0[i]++; else s1[i]++; s0[i] += s0[i-1]; s1[i] += s1[i-1]; } rep(_,Q){ int H,W; cin>>H>>W; int P; cin>>P; long long ok = 0,ng = H+W; while(ng-ok>1LL){ long long mid = (ok+ng)/2; long long x = 0,y = 0; long long rem = mid; if(rem >= N-P){ x += s0.back() - s0[P]; y += s1.back() - s1[P]; rem -= N-P; } else{ x += s0[P+rem] - s0[P]; y += s1[P+rem] - s1[P]; rem = 0; } x += s0.back() * (rem/N); y += s1.back() * (rem/N); rem %= N; x += s0[rem]; y += s1[rem]; //cout<<mid<<' '<<x<<' '<<y<<endl; if(x<H && y<W)ok = mid; else ng = mid; } // cout<<ok<<endl; cout<<(ok+P+1)%N<<endl; } return 0; }