結果
問題 | No.2359 A in S ? |
ユーザー |
![]() |
提出日時 | 2023-07-21 11:20:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 299 ms / 2,000 ms |
コード長 | 1,090 bytes |
コンパイル時間 | 2,027 ms |
コンパイル使用メモリ | 199,532 KB |
最終ジャッジ日時 | 2025-02-15 16:06:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;using pii = pair<int, int>;const int N = 1e5 + 10, B = 350;int sc[B][B], lc[N];int n, m, ans[N];vector<pii> s[N];vector<int> q[N];int main() {cin >> n >> m;for(int i = 1, l, r, x, y; i <= n; i ++) {cin >> l >> r >> x >> y;s[l].push_back({x, y});s[r + 1].push_back({-x, y});}for(int i = 1, x; i <= m; i ++) {cin >> x;q[x].push_back(i);}for(int i = 1; i < N; i ++) {for(auto [p, x] : s[i]) {int w = 1;if(p < 0) {p = -p;w = -w;}if(p < B) sc[p][x] += w;else{for(int i = 0; i * p + x < N; i ++)lc[i * p + x] += w;}}if(q[i].empty()) continue;int tot = lc[i];for(int j = 1; j < B; j ++)tot += sc[j][i % j];for(auto x : q[i]) {ans[x] = tot;}}for(int i = 1; i <= m; i ++)cout << ans[i] << "\n";}