結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー | chaemon |
提出日時 | 2016-12-19 00:27:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 167 ms / 5,000 ms |
コード長 | 2,076 bytes |
コンパイル時間 | 816 ms |
コンパイル使用メモリ | 89,136 KB |
実行使用メモリ | 24,624 KB |
最終ジャッジ日時 | 2023-08-23 13:18:58 |
合計ジャッジ時間 | 6,321 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,500 KB |
testcase_01 | AC | 2 ms
5,428 KB |
testcase_02 | AC | 3 ms
8,276 KB |
testcase_03 | AC | 6 ms
5,716 KB |
testcase_04 | AC | 8 ms
5,728 KB |
testcase_05 | AC | 8 ms
5,724 KB |
testcase_06 | AC | 10 ms
5,760 KB |
testcase_07 | AC | 10 ms
5,900 KB |
testcase_08 | AC | 11 ms
5,968 KB |
testcase_09 | AC | 5 ms
5,672 KB |
testcase_10 | AC | 8 ms
5,652 KB |
testcase_11 | AC | 5 ms
5,576 KB |
testcase_12 | AC | 12 ms
6,112 KB |
testcase_13 | AC | 7 ms
6,000 KB |
testcase_14 | AC | 4 ms
5,668 KB |
testcase_15 | AC | 4 ms
5,740 KB |
testcase_16 | AC | 11 ms
5,992 KB |
testcase_17 | AC | 10 ms
5,820 KB |
testcase_18 | AC | 10 ms
5,844 KB |
testcase_19 | AC | 3 ms
5,492 KB |
testcase_20 | AC | 11 ms
5,880 KB |
testcase_21 | AC | 4 ms
5,468 KB |
testcase_22 | AC | 2 ms
5,540 KB |
testcase_23 | AC | 65 ms
8,228 KB |
testcase_24 | AC | 65 ms
8,288 KB |
testcase_25 | AC | 64 ms
8,456 KB |
testcase_26 | AC | 65 ms
8,324 KB |
testcase_27 | AC | 64 ms
8,288 KB |
testcase_28 | AC | 64 ms
8,460 KB |
testcase_29 | AC | 65 ms
8,292 KB |
testcase_30 | AC | 64 ms
8,236 KB |
testcase_31 | AC | 65 ms
8,228 KB |
testcase_32 | AC | 65 ms
8,348 KB |
testcase_33 | AC | 161 ms
24,624 KB |
testcase_34 | AC | 163 ms
24,620 KB |
testcase_35 | AC | 163 ms
24,524 KB |
testcase_36 | AC | 167 ms
24,580 KB |
testcase_37 | AC | 167 ms
24,576 KB |
testcase_38 | AC | 151 ms
23,208 KB |
testcase_39 | AC | 150 ms
23,188 KB |
testcase_40 | AC | 149 ms
23,340 KB |
testcase_41 | AC | 149 ms
23,120 KB |
testcase_42 | AC | 152 ms
23,180 KB |
testcase_43 | AC | 151 ms
23,108 KB |
testcase_44 | AC | 151 ms
23,232 KB |
testcase_45 | AC | 149 ms
23,208 KB |
testcase_46 | AC | 147 ms
23,208 KB |
testcase_47 | AC | 150 ms
23,124 KB |
testcase_48 | AC | 2 ms
5,468 KB |
testcase_49 | AC | 2 ms
5,636 KB |
testcase_50 | AC | 150 ms
23,296 KB |
testcase_51 | AC | 150 ms
23,116 KB |
ソースコード
// #includes {{{ #include <algorithm> #include <numeric> #include <iostream> #include <string> #include <vector> #include <queue> #include <list> #include <deque> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cassert> #include <cstring> #include <cmath> using namespace std; // }}} // pre-written code {{{ #define REP(i,n) for(int i=0;i<(int)(n);++i) #define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i) #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i) #define LET(x,a) __typeof(a) x(a) //#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i) #define ALL(c) (c).begin(), (c).end() #define MP make_pair #define EXIST(e,s) ((s).find(e)!=(s).end()) #define RESET(a) memset((a),0,sizeof(a)) #define SET(a) memset((a),-1,sizeof(a)) #define PB push_back #define DEC(it,command) __typeof(command) it=command //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl; const int INF=0x3f3f3f3f; typedef long long Int; typedef unsigned long long uInt; #ifdef __MINGW32__ typedef double rn; #else typedef long double rn; #endif typedef pair<int,int> pii; /* #ifdef MYDEBUG #include"debug.h" #include"print.h" #endif */ // }}} const int D = 1000010; const uInt P = 1000000009ull; int N,Q; uInt pm[D],hsum[D]; int main(){ cin>>N>>Q; uInt h = 0ull, pw = 1ull; for(int i=0;i<=N;i++){ hsum[i] = h; pm[i] = pw; h*=P; h+=1ull; pw*=P; } map<uInt,int> mp; h = 0ull; mp[h] = 0; REP(i,Q){ char c; cin>>c; if(c=='!'){ int L,R,K; cin>>L>>R>>K; // cerr<<L<<" "<<R<<" "<<K<<endl; h+=pm[L]*hsum[R-L]*((uInt)K); /* dump(pm[L]); dump(hsum[R-L]); dump((uInt)K) */ // cerr<<i+1<<" "<<h<<endl; if(mp.find(h)==mp.end())mp[h] = i+1; }else{ // cerr<<h<<endl; cout<<mp[h]<<endl; } } return 0; }