結果
問題 | No.2359 A in S ? |
ユーザー |
|
提出日時 | 2023-06-23 22:00:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 1,852 bytes |
コンパイル時間 | 2,251 ms |
コンパイル使用メモリ | 197,896 KB |
最終ジャッジ日時 | 2025-02-15 01:01:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1e9; const int B = 240; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; // have some of those? vector<array<int,4>> arr(n); for(auto& [l,r,x,y] : arr) { cin >> l >> r >> x >> y; int k = (l-y+x-1)/x; l = k*x+y; if(r<y) { r=-1; } else { k = (r-y)/x; r = k*x+y; } if(l>r) { l=-1,r=-1,x=-1,y=-1; } } vi a(m); for(auto& i : a) { cin >> i; } // only ones that have x very small are bad. vi ans(m); for(int x=1;x<=B;++x) { vi p(mxN+B+1); for(auto [l,r,xx,y] : arr) { if(x==xx) { p[l]+=1; p[r+x]-=1; } } for(int i=x;i<p.size();++i) p[i]+=p[i-x]; for(int i=0;i<m;++i) { ans[i]+=p[a[i]]; } } vi cnt(mxN); for(auto [l,r,x,y] : arr) { if(x>B) { for(int i=l;i<=r;i+=x) { cnt[i]+=1; } } } for(int i=0;i<m;++i) { int x = a[i]; cout << ans[i]+cnt[x] << '\n'; } }