結果

問題 No.2359 A in S ?
ユーザー erbowl
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0