QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #506751 | #1877. Matryoshka Dolls | propane | WA | 81ms | 11928kb | C++20 | 8.5kb | 2024-08-05 21:12:50 | 2024-08-05 21:12:50 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<set>
#include<algorithm>
#include<cassert>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5;
namespace BIT{
LL tr[maxn];
int lowbit(int x){
return x & -x;
}
void modify(int x, int v){
while(x < maxn){
tr[x] += v;
x += lowbit(x);
}
}
LL query(int x){
LL ans = 0;
while(x){
ans += tr[x];
x -= lowbit(x);
}
return ans;
}
LL query(int l, int r){
return query(r) - query(l - 1);
}
}
const int INF = 0x3f3f3f3f;
// min
namespace ST1{
int tr[maxn * 4];
void modify(int u, int l, int r, int x, int v){
if (l == r){
tr[u] = v;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(2 * u, l, mid, x, v);
else modify(2 * u + 1, mid + 1, r, x, v);
tr[u] = min(tr[2 * u], tr[2 * u + 1]);
}
int query(int u, int l, int r, int L, int R){
if (l > R or r < L) return INF;
if (l >= L and r <= R) return tr[u];
int mid = (l + r) / 2;
return min(query(2 * u, l, mid, L, R), query(2 * u + 1, mid + 1, r, L, R));
}
}
// max
namespace ST2{
int tr[maxn * 4];
void modify(int u, int l, int r, int x, int v){
if (l == r){
tr[u] = v;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(2 * u, l, mid, x, v);
else modify(2 * u + 1, mid + 1, r, x, v);
tr[u] = max(tr[2 * u], tr[2 * u + 1]);
}
int query(int u, int l, int r, int L, int R){
if (l > R or r < L) return 0;
if (l >= L and r <= R) return tr[u];
int mid = (l + r) / 2;
return max(query(2 * u, l, mid, L, R), query(2 * u + 1, mid + 1, r, L, R));
}
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
memset(ST1::tr, 0x3f, sizeof ST1::tr);
int n, q;
cin >> n >> q;
vector<int> a(n + 1), p(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
p[a[i]] = i;
}
vector<array<int, 3> > query;
vector<LL> ans(q);
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
if (l == r){
ans[i] = 0;
}
else{
query.push_back({l, r, i});
}
}
auto solve = [&](auto &&solve, int l, int r, vector<array<int, 3> > query) -> void {
if (query.empty()) return;
int mid = (l + r) / 2;
vector<array<int, 3> > ql, qr, cur;
for(auto [l, r, id] : query){
if (r <= mid) ql.push_back({l, r, id});
else if (l > mid) qr.push_back({l, r, id});
else cur.push_back({l, r, id});
}
solve(solve, l, mid, ql);
solve(solve, mid + 1, r, qr);
if (cur.empty()) return;
{
LL sum = 0;
set<int> s;
vector<pair<int, int> > pos;
auto get = [&](int L, int R, int sign){
int x = ST1::query(1, 1, n, L, R);
int d = abs(p[L] - p[R]);
sum += d;
if (x <= r){
int v = sign * (-d + mid - p[L] + mid - p[R]);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto get_last = [&](int val, int sign){
int x = ST1::query(1, 1, n, val, n);
if (x <= r){
int v = sign * (mid - p[val]);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto get_first = [&](int val, int sign){
int x = ST1::query(1, 1, n, 1, val);
if (x <= r){
int v = sign * (mid - p[val]);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto add = [&](int x){
if (s.empty()){
s.insert(x);
get_last(x, 1);
get_first(x, 1);
return;
}
auto nxt = s.upper_bound(x);
if (nxt == s.end()){
auto pre = prev(nxt);
get_last(*pre, -1);
get_last(x, 1);
get(*pre, x, 1);
}
else{
if (nxt == s.begin()){
get_first(*nxt, -1);
get_first(x, 1);
get(x, *nxt, 1);
}
else{
auto pre = prev(nxt);
get(*pre, *nxt, -1);
get(*pre, x, 1);
get(x, *nxt, 1);
}
}
s.insert(x);
};
for(int i = mid + 1; i <= r; i++){
ST1::modify(1, 1, n, a[i], i);
}
sort(cur.begin(), cur.end(), [&](auto &&a, auto &&b){
return a[0] > b[0];
});
for(int i = mid, j = 0; i >= l; i--){
add(a[i]);
while(j < cur.size() and cur[j][0] == i){
auto [l, r, id] = cur[j++];
ans[id] += sum + BIT::query(mid + 1, r);
}
}
for(int i = mid + 1; i <= r; i++){
ST1::modify(1, 1, n, a[i], INF);
}
for(auto [x, v] : pos) BIT::modify(x, -v);
}
{
LL sum = 0;
set<int> s;
vector<pair<int, int> > pos;
auto get = [&](int L, int R, int sign){
int x = ST2::query(1, 1, n, L, R);
int d = abs(p[L] - p[R]);
sum += d;
if (x >= l){
int v = sign * (-d + p[L] - mid + p[R] - mid);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto get_last = [&](int val, int sign){
int x = ST2::query(1, 1, n, val, n);
if (x >= l){
int v = sign * (p[val] - mid);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto get_first = [&](int val, int sign){
int x = ST2::query(1, 1, n, 1, val);
if (x >= l){
int v = sign * (p[val] - mid);
BIT::modify(x, v);
pos.push_back({x, v});
}
};
auto add = [&](int x){
if (s.empty()){
s.insert(x);
get_last(x, 1);
get_first(x, 1);
return;
}
auto nxt = s.upper_bound(x);
if (nxt == s.end()){
auto pre = prev(nxt);
get_last(*pre, -1);
get_last(x, 1);
get(*pre, x, 1);
}
else{
if (nxt == s.begin()){
get_first(*nxt, -1);
get_first(x, 1);
get(x, *nxt, 1);
}
else{
auto pre = prev(nxt);
get(*pre, *nxt, -1);
get(*pre, x, 1);
get(x, *nxt, 1);
}
}
s.insert(x);
};
for(int i = l; i <= mid; i++){
ST2::modify(1, 1, n, a[i], i);
}
sort(cur.begin(), cur.end(), [&](auto &&a, auto &&b){
return a[1] < b[1];
});
for(int i = mid + 1, j = 0; i <= r; i++){
add(a[i]);
while(j < cur.size() and cur[j][1] == i){
auto [l, r, id] = cur[j++];
ans[id] += sum + BIT::query(l, mid);
}
}
for(int i = l; i <= mid; i++){
ST2::modify(1, 1, n, a[i], 0);
}
for(auto [x, v] : pos) BIT::modify(x, -v);
}
};
solve(solve, 1, n, query);
for(auto x : ans) cout << x << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5732kb
input:
5 5 1 5 2 4 3 1 5 1 4 1 3 1 2 1 1
output:
7 5 3 1 0
result:
ok 5 number(s): "7 5 3 1 0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6156kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 81ms
memory: 11928kb
input:
100000 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...
output:
4999950000
result:
ok 1 number(s): "4999950000"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5580kb
input:
20 1 12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7 9 18
output:
40
result:
wrong answer 1st numbers differ - expected: '36', found: '40'