#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define eb emplace_back
typedef long long ll;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
const int MAXN = 1e6 + 15;
const int ADD = 1e6;
int t[4 * MAXN], tadd[4 * MAXN];
int f[MAXN];
void Update(int pos, int val) {
for(;pos < MAXN; pos = (pos | (pos + 1))) {
f[pos] += val;
}
}
int Sum(int pos) {
int ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1) {
ans += f[pos];
}
return ans;
}
void Push(int v, int vl, int vr) {
if (tadd[v]) {
t[v] += tadd[v];
if (vl != vr) {
tadd[2 * v + 1] += tadd[v];
tadd[2 * v + 2] += tadd[v];
}
tadd[v] = 0;
}
}
void Update(int l, int r, int val, int v = 0, int vl = 0, int vr = MAXN - 1) {
Push(v, vl, vr);
if (vr < l || r < vl) {return;}
if (vl >= l && vr <= r) {
tadd[v] += val;
Push(v, vl, vr);
return;
}
int vm = vl + (vr - vl) / 2;
Update(l, r, val, 2 * v + 1, vl, vm);
Update(l, r, val, 2 * v + 2, vm + 1, vr);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
int Query(int pos, int v = 0, int vl = 0, int vr = MAXN - 1) {
Push(v, vl, vr);
if (vl == vr) {
return t[v];
}
int vm = vl + (vr - vl) / 2;
if (pos <= vm) {
return Query(pos, 2 * v + 1, vl, vm);
}
return Query(pos, 2 * v + 2, vm + 1, vr);
}
int GetMx() {
Push(0, 0, MAXN - 1);
return t[0];
}
std::vector<int> countScans(std::vector<int> aa,std::vector<int> xx,std::vector<int> vv){
vector <ll> a, x, v, all;
int n = aa.size(), q = xx.size();
for (int i = 0; i < n; ++i) {
a.eb(aa[i] * ADD + i);
all.eb(a[i]);
}
for (int i = 0; i < xx.size(); ++i) {
x.eb(xx[i]);
v.eb(vv[i] * ADD + xx[i]);
all.eb(v[i]);
}
sort(all.begin(), all.end());
all.resize(unique(all.begin(), all.end()) - all.begin());
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
Update(a[i], 1);
}
for (int i = 0; i < n; ++i) {
Update(a[i], a[i], i);
int cntLess = Sum(a[i] - 1);
Update(a[i], a[i], -cntLess);
}
for (auto &u : v) {
u = lower_bound(all.begin(), all.end(), u) - all.begin();
}
vector <int> s;
for(int f = 0; f < q; ++f) {
int pos = x[f];
int x = a[pos];
int y = v[f];
a[pos] = y;
Update(x + 1, MAXN - 1, 1);
Update(y + 1, MAXN - 1, -1);
Update(x, -1);
Update(y, 1);
int cntLess = Sum(y - 1);
int nowVal = Query(y);
Update(y, y, -nowVal + (pos - cntLess));
s.eb(GetMx());
}
return s;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < xx.size(); ++i) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
2172 KB |
Output is correct |
| 2 |
Correct |
112 ms |
4380 KB |
Output is correct |
| 3 |
Incorrect |
193 ms |
6896 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
