結果
問題 | No.2359 A in S ? |
ユーザー | HIcoder |
提出日時 | 2023-07-02 11:08:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 525 ms / 2,000 ms |
コード長 | 1,766 bytes |
コンパイル時間 | 788 ms |
コンパイル使用メモリ | 88,612 KB |
実行使用メモリ | 254,872 KB |
最終ジャッジ日時 | 2023-09-23 07:22:28 |
合計ジャッジ時間 | 10,978 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,856 KB |
testcase_01 | AC | 5 ms
5,752 KB |
testcase_02 | AC | 21 ms
20,000 KB |
testcase_03 | AC | 6 ms
6,440 KB |
testcase_04 | AC | 503 ms
254,568 KB |
testcase_05 | AC | 515 ms
254,716 KB |
testcase_06 | AC | 483 ms
254,540 KB |
testcase_07 | AC | 525 ms
254,480 KB |
testcase_08 | AC | 516 ms
254,536 KB |
testcase_09 | AC | 488 ms
254,696 KB |
testcase_10 | AC | 495 ms
254,872 KB |
testcase_11 | AC | 510 ms
254,652 KB |
testcase_12 | AC | 491 ms
254,484 KB |
testcase_13 | AC | 481 ms
254,480 KB |
testcase_14 | AC | 480 ms
254,724 KB |
testcase_15 | AC | 485 ms
254,828 KB |
testcase_16 | AC | 486 ms
254,540 KB |
testcase_17 | AC | 487 ms
254,544 KB |
testcase_18 | AC | 494 ms
254,536 KB |
testcase_19 | AC | 490 ms
254,488 KB |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<int,int> P; typedef pair<int,P> PP; const ll MOD=1e9+7; int main(){ int N,M; cin>>N>>M; vector<int> L(N),R(N),X(N),Y(N); ll maxR=0; for(int i=0;i<N;i++){ cin>>L[i]>>R[i]>>X[i]>>Y[i]; maxR=max(1LL*R[i],maxR); } ll K=maxR+1; vector<int> A(M); for(int i=0;i<M;i++)cin>>A[i]; const ll T=max(1LL,(ll)sqrt(N)); const ll MAXA=100000+10; vector<int> cnt(MAXA+1); vector<vector<ll>> imos(T,vector<ll>(MAXA+1,0)); for(int i=0;i<N;i++){ int l=L[i]; int r=R[i]; int x=X[i]; int y=Y[i]; if(x>=T){ ll left=1LL*(L[i]-Y[i]+x-1)/x*x; for(ll t=left+y;t<=R[i];t+=X[i]){ cnt[t]++; } }else{ //x<T ll left=max(0LL,1LL*(l-y+x-1)/x*x + y); ll right=min(MAXA+1,1LL*(r-y)/x*x + y); if(l<=left && right<=r){ imos[x][left]++; if(right+x<=MAXA){ imos[x][right+x]--; } } } } for(int x=0;x<T;x++){ for(int v=1;v<=MAXA;v++){ if(v-x>=0){ imos[x][v]+=imos[x][v-x]; } } } vector<ll> num(MAXA+1,0); for(int x=0;x<T;x++){ for(int v=1;v<=MAXA;v++){ num[v]+=imos[x][v]; } } vector<ll> ans(M); for(int i=0;i<M;i++){ ans[i]=cnt[A[i]]+num[A[i]]; } for(int v:ans){ cout<<v<<endl; } }