#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <bitset>
#include <fstream>
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s
typedef long long ll;
//using namespace __gnu_pbds;
//using namespace atcoder;
using namespace std;
const ll modd = (1000LL * 1000LL * 1000LL + 7LL);
//const ll modd = 998244353;
template<class T>
class SegmentTree2 {
public:
SegmentTree2(const vector<T>& data, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) {
Initialize(data);
}
SegmentTree2(int n, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) {
vector<T> temp(n, zv);
Initialize(temp);
}
T operator[](int i) {
return tree[B+i];
}
T GetEvaluation(int L, int R) { // "min/max" on interval [L,R); 0-based indexing, as usual
if (R<=L) { return zv; }
return GetEvaluationHelper(L, R, 0, B, 1);
}
void SetVal(int i, T val) {
tree[B+i] = val;
for(int j = (B + i) / 2; j >= 1; j /= 2) {
tree[j] = f(tree[2*j], tree[2*j+1]);
}
}
private:
vector<T> tree;
int B; // power of two greater than size of input data
T zv;
function<T(T,T)> f;
void Initialize(const vector<T>& data) {
B = 1;
while(B < data.size()) {B *= 2; }
tree = std::move(vector<T>(2*B, zv));
copy(data.begin(), data.end(), next(tree.begin(), B));
for(int i = B - 1; i >= 1; --i) {
tree[i] = f(tree[2*i], tree[2*i+1]);
}
}
T GetEvaluationHelper(int L, int R, int start, int length, int tree_index) {
if (L==R) { return zv; }
if ((L==start) && (R==start+length)) { return tree[tree_index]; }
int midpoint = start + length/2;
T left_ = zv, right_ = zv;
if (L<=min(midpoint,R)) {
left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index);
}
if (max(midpoint,L)<=R) {
right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1);
}
return f(left_, right_);
}
};
template<class T, class S>
class LazySegmentTree {
// Lazy propagation segment tree, containing elts of type T; S is type ("paramter space type") for all possible function we'll be
// applying to elts (thee funcs should commute with f; f should be associative)
public:
typedef function<T(T)> application_type;
// f is combining function, should be associative; zero_value is identity for f as a grupoid operation;
// com is composition of application functions, specifically com(a1, a2) is a1 \circ a2 ie com(a1,a2)(t)=a1(a2(t))
// param is parametrization of application functions
// id_ is parameter for identity application function
// typical example if you have min segtree, and you want to assign values in a lazy way to interval:
// T=int,S=int, f(x,y) = min(x,y), zero_value = +infty"=modd"; com(a,b)=a;
// param(a) = [](int a){ return function<int(int)>([](int x){return a;}); }
// CAREFUL!!!! in param make sure if you capture anything in return function, you do it by value, not by reference!!!!!!!!!!!!!!!!!!!
// id_ = say modd+1; and param(modd+1) should be identity, and comm should accomodate that
LazySegmentTree(const vector<T>& data, function<T(T,T)> f_, T zero_value,
function<S(S,S)> com, function<application_type(S)> param, S id_) : zv(zero_value), f(f_), composition(com),
paramtrization(param), ident(id_) {
Initialize(data);
}
T operator[](int i) {
return GetEvaluation(i, i+1);
}
T GetEvaluation(int L, int R) { // "min/max" on interval [L,R); 0-based indexing, as usual
if (R<=L) { return zv; }
return GetEvaluationHelper(L, R, 0, B, 1, ident);
}
void SetVal(int L, int R, S g) { // set on interval [L,R); 0-based indexing
if (R<=L) { return; }
SetValHelper(L, R, 0, B, 1, g);
}
private:
vector<T> tree;
vector<S> application_function_below;
int B; // power of two greater than size of input data
T zv;
function<T(T,T)> f;
function<S(S,S)> composition;
function<application_type(S)> paramtrization;
S ident;
void Initialize(const vector<T>& data) {
B = 1;
while(B < data.size()) {B *= 2; }
tree = vector<T>(2*B, zv);
copy(data.begin(), data.end(), next(tree.begin(), B));
for(int i = B - 1; i >= 1; --i) {
tree[i] = f(tree[2*i], tree[2*i+1]);
}
application_function_below = vector<S>(2*B, ident);
}
T GetEvaluationHelper(int L, int R, int start, int length, int tree_index, S accumulate) {
if (L==R) { return zv; }
if ((L==start) && (R==start+length)) { return paramtrization(accumulate)(tree[tree_index]); }
int midpoint = start + length/2;
T left_ = zv, right_ = zv;
if (L<=min(midpoint,R)) {
left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index, composition(accumulate, application_function_below[tree_index]));
}
if (max(midpoint,L)<=R) {
right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1, composition(accumulate, application_function_below[tree_index]));
}
return f(left_, right_);
}
void SetValHelper(int L, int R, int start, int length, int tree_index, S g) {
if (L==R) { return; }
if ((L==start) && (R==start+length)) {
tree[tree_index] = paramtrization(g)(tree[tree_index]);
application_function_below[tree_index] = composition(g, application_function_below[tree_index]);
return; }
int midpoint = start + length/2;
application_function_below[2*tree_index] = composition(application_function_below[tree_index], application_function_below[2*tree_index]);
application_function_below[2*tree_index+1] = composition(application_function_below[tree_index], application_function_below[2*tree_index+1]);
tree[2*tree_index] = paramtrization(application_function_below[tree_index])(tree[2*tree_index]);
tree[2*tree_index+1] = paramtrization(application_function_below[tree_index])(tree[2*tree_index+1]);
application_function_below[tree_index] = ident;
if (L<=min(midpoint,R)) {
SetValHelper(L, min(midpoint,R), start, length/2, 2*tree_index, g);
}
if (max(midpoint,L)<=R) {
SetValHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1, g);
}
tree[tree_index] = f(tree[2*tree_index], tree[2*tree_index+1]);
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
map<int,int> dict;
for(auto x : A) { dict[x] = 0; }
for(auto x : V) { dict[x] = 0; }
int i = 0;
for(auto it = dict.begin(); it != dict.end(); ++it) {
it->second = i; ++i;
}
for(auto& x : A) { x = dict[x]; }
for(auto& x : V) { x = dict[x]; }
vector<ll> initial(dict.size(), -modd);
vector<int> a_copy(A);
sort(a_copy.begin(), a_copy.end());
vector<int> count_(dict.size(), 0);
vector<set<int>> rightmost(dict.size());
forr(i,0,A.size()) {
int k = upper_bound(a_copy.begin(), a_copy.end(), A[i]) - a_copy.begin();
--k;
initial[A[i]] = i-k;
++count_[A[i]];
rightmost[A[i]].insert(i);
}
LazySegmentTree<ll,ll> segtree(initial, [](ll x, ll y){ return max(x,y); }, -modd*modd,
[](ll a, ll b){ return a+b; }, [](ll a){ return [a](int x){ return x+a; }; }, 0);
SegmentTree2<int> counttree(count_, [](int x, int y){ return x+y; }, 0);
int Q=X.size();
std::vector<int> answer(Q);
for (int j=0;j<Q;j++) {
if (A[X[j]]==V[j]) {
answer[j] = segtree.GetEvaluation(0, initial.size());
continue;
}
if (V[j]<A[X[j]]) {
segtree.SetVal(V[j], A[X[j]], -1);
} else {
segtree.SetVal(A[X[j]], V[j], +1);
}
rightmost[A[X[j]]].erase(X[j]);
rightmost[V[j]].insert(X[j]);
counttree.SetVal(A[X[j]], counttree[A[X[j]]] - 1);
counttree.SetVal(V[j], counttree[V[j]]+1);
int p = segtree[A[X[j]]];
int new_val = *prev(rightmost[A[X[j]]].end())-(counttree.GetEvaluation(0, A[X[j]]+1)-1);
segtree.SetVal(A[X[j]], A[X[j]]+1, -p+ new_val);
p = segtree[V[j]];
new_val = *prev(rightmost[V[j]].end())-(counttree.GetEvaluation(0, V[j]+1)-1);
segtree.SetVal(V[j], V[j]+1, -p+ new_val);
A[X[j]] = V[j];
answer[j] = segtree.GetEvaluation(0, initial.size());
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:24:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
| ^
bubblesort2.cpp:219:5: note: in expansion of macro 'forr'
219 | forr(i,0,A.size()) {
| ^~~~
bubblesort2.cpp: In instantiation of 'void LazySegmentTree<T, S>::Initialize(const std::vector<_Tp>&) [with T = long long int; S = long long int]':
bubblesort2.cpp:125:11: required from 'LazySegmentTree<T, S>::LazySegmentTree(const std::vector<_Tp>&, std::function<T(T, T)>, T, std::function<S(S, S)>, std::function<std::function<T(T)>(S)>, S) [with T = long long int; S = long long int]'
bubblesort2.cpp:227:86: required from here
bubblesort2.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | while(B < data.size()) {B *= 2; }
| ~~^~~~~~~~~~~~~
bubblesort2.cpp: In instantiation of 'void SegmentTree2<T>::Initialize(const std::vector<_Tp>&) [with T = int]':
bubblesort2.cpp:46:11: required from 'SegmentTree2<T>::SegmentTree2(const std::vector<_Tp>&, std::function<T(T, T)>, T) [with T = int]'
bubblesort2.cpp:228:75: required from here
bubblesort2.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while(B < data.size()) {B *= 2; }
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
1892 KB |
Output is correct |
| 2 |
Correct |
95 ms |
3020 KB |
Output is correct |
| 3 |
Correct |
179 ms |
4716 KB |
Output is correct |
| 4 |
Correct |
178 ms |
4728 KB |
Output is correct |
| 5 |
Correct |
180 ms |
4796 KB |
Output is correct |
| 6 |
Correct |
166 ms |
4676 KB |
Output is correct |
| 7 |
Correct |
189 ms |
4744 KB |
Output is correct |
| 8 |
Correct |
173 ms |
4676 KB |
Output is correct |
| 9 |
Correct |
180 ms |
4872 KB |
Output is correct |
| 10 |
Runtime error |
38 ms |
9020 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
