結果
問題 | No.1270 Range Arrange Query |
ユーザー | 👑 Nachia |
提出日時 | 2020-10-23 23:36:28 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,137 ms / 7,000 ms |
コード長 | 3,390 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 184,252 KB |
実行使用メモリ | 5,308 KB |
最終ジャッジ日時 | 2023-09-28 18:52:28 |
合計ジャッジ時間 | 8,544 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 71 ms
4,376 KB |
testcase_07 | AC | 601 ms
4,376 KB |
testcase_08 | AC | 109 ms
4,380 KB |
testcase_09 | AC | 412 ms
4,376 KB |
testcase_10 | AC | 454 ms
4,420 KB |
testcase_11 | AC | 1,137 ms
5,116 KB |
testcase_12 | AC | 1,124 ms
5,172 KB |
testcase_13 | AC | 1,130 ms
5,236 KB |
testcase_14 | AC | 48 ms
5,184 KB |
testcase_15 | AC | 66 ms
5,128 KB |
testcase_16 | AC | 66 ms
5,308 KB |
testcase_17 | AC | 67 ms
5,156 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL = long long; using ULL = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) template< class S, S(*op)(S a, S b), S(*e)() > struct segtree { private: int N; vector<S> V; public: segtree(int n) { N = 1; while (N < n) N *= 2; V.assign(N * 2, e()); } segtree(vector<S> A) { N = 1; while (N < A.size()) N *= 2; V.assign(N * 2, e()); rep(i, A.size()) V[N + i] = A[i]; for (int i = N - 1; i >= 1; i--) V[i] = op(V[i * 2], V[i * 2 + 1]); } void set(int p, S v) { p += N; V[p] = v; while (p != 1) { p /= 2; V[p] = op(V[p * 2], V[p * 2 + 1]); } } S get(int p) { p += N; return V[p]; } S prod(int l, int r) { S ans_l = e(), ans_r = e(); l += N; r += N; while (l < r) { if (l & 1) ans_l = op(ans_l, V[l++]); if (r & 1) ans_r = op(V[--r], ans_r); l /= 2; r /= 2; } return op(ans_l, ans_r); } }; struct S { int a, b, x; }; S op(S l, S r) { S res; res.a = l.a + r.a; res.b = l.b + r.b; res.x = min(min(l.b + r.x, l.x + r.a), l.b + r.a); return res; } S e() { return { 0, 0, 100000000 }; } using RQ = segtree<S, op, e>; struct S2 { int a; }; S2 op2(S2 l, S2 r) { S2 res; res.a = l.a + r.a; return res; } S2 e2() { return { 0 }; } using RQ2 = segtree<S2, op2, e2>; int N, Q; pair<int, int> A[20000]; int I[20000]; RQ G(1); RQ2 GL(1), GR(1); int mo_l = 0; int mo_r = 0; int mo_reverses = 0; void moverange(int l, int r) { for (; mo_l > l; mo_l--) { G.set(I[mo_l - 1], { 0,0,0 }); GL.set(I[mo_l - 1], { 0 }); mo_reverses += GR.prod(0, I[mo_l - 1]).a; mo_reverses += GL.prod(I[mo_l - 1] + 1, N).a; } for (; mo_r < r; mo_r++) { G.set(I[mo_r], { 0,0,0 }); GR.set(I[mo_r], { 0 }); mo_reverses += GR.prod(0, I[mo_r]).a; mo_reverses += GL.prod(I[mo_r] + 1, N).a; } for (; mo_l < l; mo_l++) { G.set(I[mo_l], { 1,0,0 }); GL.set(I[mo_l], { 1 }); mo_reverses -= GR.prod(0, I[mo_l]).a; mo_reverses -= GL.prod(I[mo_l] + 1, N).a; } for (; mo_r > r; mo_r--) { G.set(I[mo_r - 1], { 0,1,0 }); GR.set(I[mo_r - 1], { 1 }); mo_reverses -= GR.prod(0, I[mo_r - 1]).a; mo_reverses -= GL.prod(I[mo_r - 1] + 1, N).a; } } int TotalReverses = 0; struct Query { int l, r, i; bool operator<(Query b) const { return r < b.r; } }; vector<Query> queries[100]; int ans[20000]; int main() { cin >> N >> Q; rep(i, N) { int a; cin >> a; A[i] = { a,i }; } sort(A, A + N); rep(i, N) I[A[i].second] = i; rep(q, Q) { int l, r; cin >> l >> r; l--; queries[l / 200].push_back({ l,r,q }); } rep(i, 100) sort(queries[i].begin(), queries[i].end()); G = RQ(vector<S>(N, S{ 0,0,0 })); GL = RQ2(vector<S2>(N, S2{ 0 })); GR = RQ2(vector<S2>(N, S2{ 1 })); moverange(0, N); TotalReverses = mo_reverses; rep(i, 100) { for (auto q : queries[i]) { moverange(q.l, q.r); ans[q.i] = TotalReverses - mo_reverses + G.prod(0, N).x * (q.r - q.l); } } rep(i, Q) cout << ans[i] << endl; return 0; }