結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー |
![]() |
提出日時 | 2019-07-10 05:32:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 567 ms / 5,000 ms |
コード長 | 1,648 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 107,384 KB |
実行使用メモリ | 19,684 KB |
最終ジャッジ日時 | 2024-10-13 08:29:13 |
合計ジャッジ時間 | 14,924 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;ll mod[3]={1000000007, 1000000009, 998244353};ll b0[2]={314159265, 358979323};ll powmod(ll a, ll k, ll MOD){ll ap=a, ans=1;while(k){if(k&1){ans*=ap;ans%=MOD;}ap=ap*ap;ap%=MOD;k>>=1;}return ans;}ll inv(ll a, ll MOD){return powmod(a, MOD-2, MOD);}int n;ll p[1000010];int main(){int q; cin>>n>>q;char c[100010];ll l[100010], r[100010], k[100010];for(int i=1; i<=q; i++){cin>>c[i];if(c[i]=='!') cin>>l[i]>>r[i]>>k[i];}int ans[100010]={};for(int t=0; t<6; t++){ll b=b0[t%2], MOD=mod[t%3];ll bv=inv(b-1, MOD);p[0]=1;for(int i=1; i<n; i++) p[i]=p[i-1]*b%MOD;ll s=0;map<ll, int> mp;mp[0]=0;for(int i=1; i<=q; i++){if(c[i]=='!'){(s+=(k[i]+MOD)*(p[r[i]]-p[l[i]]+MOD)%MOD*bv)%=MOD;if(mp.find(s)==mp.end()){mp[s]=i;}}else{ans[i]=max(ans[i], mp[s]);}}}for(int i=1; i<=q; i++){if(c[i]=='?') cout<<ans[i]<<endl;}return 0;}