#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 5e5 + 100;
ll eff[mxn];
template <class type1>
using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;
struct Node {
ordered_multiset<ll> inc, dec;
};
vector<int> A;
vector<pair<int, int>> og;
struct SGT {
vector<Node> sgt;
SGT(int sz) {
sgt.resize(4 * sz);
}
void del(int k, ll val) {
sgt[k].inc.erase(sgt[k].inc.lower_bound(val));
sgt[k].dec.erase(sgt[k].dec.lower_bound(-val));
}
void add(int k, ll val) {
sgt[k].inc.insert(val);
sgt[k].dec.insert(-val);
}
void build(int k, int l, int r) {
if (l == r) {
add(k, A[l]);
return;
}
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
}
void update(int k, int l, int r, int i, ll val) {
if (l > i || r < i) return;
del(k, A[i]);
add(k, val);
if (l == r) return;
int mid = (l + r) / 2;
update(k * 2, l, mid, i, val);
update(k * 2 + 1, mid + 1, r, i, val);
}
ll getL(int k, int l, int r, int i) {
if (l > i) return 0;
if (r <= i) return sgt[k].dec.order_of_key(-A[i]);
int mid = (l + r) / 2;
return getL(k * 2, l, mid, i) + getL(k * 2 + 1, mid + 1, r, i);
}
ll getR(int k, int l, int r, int i) {
if (r < i) return 0;
if (l >= i) return sgt[k].inc.order_of_key(A[i]);
int mid = (l + r) / 2;
return getR(k * 2, l, mid, i) + getR(k * 2 + 1, mid + 1, r, i);
}
} sgt(mxn);
ll merge(int l, int r) {
ll ans = 0;
int mid = (l + r) / 2;
vector<pair<ll, ll>> vl, vr;
for (int i = l; i <= mid; i++) vl.push_back(og[i]);
for (int i = mid + 1; i <= r; i++) vr.push_back(og[i]);
int pl = 0, pr = 0;
int cnt = l;
while (pl < vl.size() && pr < vr.size()) {
if (vl[pl].first <= vr[pr].first) og[cnt++] = vl[pl++];
else {
ans += vl.size() - pl;
eff[vr[pr].second] += vl.size() - pl;
og[cnt++] = vr[pr++];
}
}
while (pl < vl.size()) og[cnt++] = vl[pl++];
while (pr < vr.size()) og[cnt++] = vr[pr++];
return ans;
}
ll ms(int l, int r) {
if (l == r) return 0;
int mid = (l + r) / 2;
ms(l, mid);
ms(mid + 1, r);
return merge(l, r);
}
vector<int> countScans(vector<int> _A, vector<int> X, vector<int> V){
A = _A;
int Q = X.size(), N = A.size();
for (int i = 0; i < N; i++) og.push_back({A[i], i});
vector<int> answer(Q);
ll ans = ms(0, N - 1);
for (int i = 0; i < Q; i++) {
ans -= eff[X[i]];
A[X[i]] = V[i];
ll get = sgt.getL(1, 0, N - 1, X[i]) + sgt.getR(1, 0, N - 1, X[i]);
ans += get;
eff[X[i]] = get;
answer[i] = ans;
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'long long int merge(int, int)':
bubblesort2.cpp:88:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | while (pl < vl.size() && pr < vr.size()) {
| ~~~^~~~~~~~~~~
bubblesort2.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | while (pl < vl.size() && pr < vr.size()) {
| ~~~^~~~~~~~~~~
bubblesort2.cpp:96:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | while (pl < vl.size()) og[cnt++] = vl[pl++];
| ~~~^~~~~~~~~~~
bubblesort2.cpp:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | while (pr < vr.size()) og[cnt++] = vr[pr++];
| ~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
252 ms |
376148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
252 ms |
376148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
310 ms |
377632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
252 ms |
376148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
