結果
問題 | No.2359 A in S ? |
ユーザー |
|
提出日時 | 2023-06-26 19:23:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,070 ms / 2,000 ms |
コード長 | 1,532 bytes |
コンパイル時間 | 2,066 ms |
コンパイル使用メモリ | 202,204 KB |
最終ジャッジ日時 | 2025-02-15 02:25:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;#define int long longsigned main(){ll n,m;std::cin >> n>>m;vector<tuple<ll,ll,ll,ll>> q(n);for (int i = 0; i < n; i++) {ll l,r,x,y;std::cin >> l>>r>>x>>y;q[i] = {l,r,x,y};}vector<ll> a(m);for (int i = 0; i < m; i++) {std::cin >> a[i];}vector<ll> ans(100001);vector<vector<ll>> imos(100003,vector<ll>(320));for (int i = 0; i < n; i++) {auto [l,r,x,y] = q[i];if(x>=320){while(y<=100000){if(l<=y&&y<=r){ans[y]++;}y+= x;}continue;}ll st = max(0ll, (l-y+x-1)/x*x+y);ll en = min(100000ll, (r-y)/x*x+y);if(st<l)continue;if(r<st)continue;imos[st][x]++;if(en+x<=100000)imos[en+x][x]--;}// for (int j = 100; j <= 100; j++) {// for (int i = 0; i <= 100; i++) {// std::cout << imos[i][j]<<" ";// }// std::cout << std::endl;// }for (int i = 1; i < 320; i++) {for (int j = 1; j <= 100000; j++) {if(j-i>=0)imos[j][i] += imos[j-i][i];}}for (int j = 1; j <= 100000; j++) {for (int i = 1; i < 320; i++) {ans[j] += imos[j][i];}}for (int i = 0; i < m; i++) {std::cout << ans[a[i]] << std::endl;}}