結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー |
|
提出日時 | 2016-12-19 22:09:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 208 ms / 5,000 ms |
コード長 | 1,782 bytes |
コンパイル時間 | 2,183 ms |
コンパイル使用メモリ | 178,056 KB |
実行使用メモリ | 24,836 KB |
最終ジャッジ日時 | 2024-12-21 16:51:03 |
合計ジャッジ時間 | 7,109 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N, Q; void init(){ cin >> N >> Q; } const int HASH_T = 3; const int MAXN = ( int ) 1e6; int base[ HASH_T ] = { 10003, 10007, 10009 }; int base_psum[ HASH_T ][ MAXN + 1 ]; int mod[ HASH_T ] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9, 1114111 }; void preprocess(){ for( int t = 0; t < HASH_T; ++t ){ int cb = 1; for( int i = 0; i < N; ++i ){ base_psum[ t ][ i + 1 ] = ( base_psum[ t ][ i ] + cb ) % mod[ t ]; cb = 1LL * cb * base[ t ] % mod[ t ]; } } } void solve(){ map< vi, int > earliest; vi chv( HASH_T ); // current hash values earliest[ chv ] = 0; for( int i = 0; i < Q; ++i ){ string op; cin >> op; if( op == "!" ){ int L, R, K; cin >> L >> R >> K; for( int t = 0; t < HASH_T; ++t ){ int diff = ( base_psum[ t ][ R ] - base_psum[ t ][ L ] ) % mod[ t ]; diff = 1LL * diff * K % mod[ t ]; ( chv[ t ] += diff ) %= mod[ t ]; if( chv[ t ] < 0 ) chv[ t ] += mod[ t ]; } if( not earliest.count( chv ) ) earliest[ chv ] = i + 1; } else{ cout << earliest[ chv ] << endl; } } } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }