結果
問題 |
No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
|
ユーザー |
![]() |
提出日時 | 2022-12-17 20:32:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 5,000 ms |
コード長 | 1,523 bytes |
コンパイル時間 | 7,113 ms |
実行使用メモリ | 10,884 KB |
スコア | 16,092,896,139 |
最終ジャッジ日時 | 2022-12-17 20:38:49 |
合計ジャッジ時間 | 68,202 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 120 |
ソースコード
// #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; #define rep(i, n) for (int i=0; i<(int)(n); ++(i)) #define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i)) #define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i)) #define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i)) #define all(x) (x).begin(), (x).end() const int INF = (int)(1e9); int main() { int n, q, wt, st; cin >> n >> q >> wt >> st; vector<int> w(n), sum(n+1); rep(i, n) cin >> w[i]; rep(i, n) sum[i+1] += sum[i] + w[i]; vector<int> l(q), r(q); rep(i, q) cin >> l[i] >> r[i]; int blen = (int)ceil(sqrt(q)), m = (n+1+blen-1) / blen; vector<vector<tuple<int, int, int>>> blst(m); rep(i, q) blst[l[i]/blen].emplace_back(r[i], l[i], i); int scnt = 0; rep(i, m) if (!blst[i].empty()) { if (scnt%2 == 0) sort(all(blst[i])); else sort(blst[i].rbegin(), blst[i].rend()); ++scnt; } vector<int> p(q); int pid = 0; rep(i, m) for (const auto& pi : blst[i]) { p[pid] = get<2>(pi); ++pid; } int li = 0, ri = 0; bool fir = true; ll res = 0; rep(i, m) for (const auto& pi : blst[i]) { int nri = get<0>(pi), nli = get<1>(pi); if (fir) { res += sum[nri] - sum[nli-1]; li = nli; ri = nri; fir = false; } else { int ai = min(li, nli), bi = max(li, nli), ci = min(ri, nri), di = max(ri, nri); res += (sum[bi-1]-sum[ai-1]) + (sum[di-1]-sum[ci-1]); li = nli; ri = nri; } } rep(i, q) cout << (p[i]+1) << (i<q-1?' ':'\n'); return 0; }