#include <bits/stdc++.h>
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
#ifdef ONLINE_JUDGE
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define __f(...) 0
#endif
}
/*
* Treaps Implementation
* prior is priority which gives heap property
* key gives BST property
* size is size of our tree
* sum is sum of our subtree
* lazy is lazy value
* val is value stored at that node
* source:
https://tanujkhattar.wordpress.com/2016/01/10/treaps-one-tree-to-rule-em-all-part-2/
https://www.codechef.com/viewsolution/36079099
* verification:
https://www.spoj.com/status/HORRIBLE,deepkamal/
*/
// currently not considering reverse
// confirmed for max as well as min.
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(){
return uniform_int_distribution<int>(0,1e9)(rng) ;
}
struct node{
int prior, size, val, mx, mn, lazy, key;
//bool rev ;
node *l, *r;
node ():l(nullptr) , r(nullptr) {}
};
node* newnode(int k,int _val){
node *ret ; ret = new node();
ret->key = k ;
ret->val = ret->mx = ret->mn = _val;
ret->lazy = 0 ;
ret->size = 1 ;
ret->prior = Random() ;
return ret ;
}
typedef node* pnode;
const int inf = 1e15;
struct IMPLICIT_TREAP {
node *tree;
IMPLICIT_TREAP(): tree (nullptr) { }
int SZ(pnode t){
return t ? t->size : 0 ;
}
void upd_sz(pnode t){
if(t){ t->size = SZ(t->l) + 1 + SZ(t->r); }
}
void combine(pnode& t,pnode l,pnode r){//combine segtree ranges
t->mx = -inf, t->mn = inf;
if(l) ckmax(t->mx,l->mx),ckmin(t->mn,l->mn);
if(r) ckmax(t->mx,r->mx),ckmin(t->mn,r->mn);
}
void propagate(pnode t){
if(!t or !t->lazy) return ; // here this implementation is for sum so t->lazy != 0
t->val += t->lazy ; //operation of lazy
t->mn += t->lazy;
t->mx += t->lazy;
if(t->l) t->l->lazy += t->lazy ; //propagate lazy for t's children
if(t->r) t->r->lazy += t->lazy ;
t->lazy = 0;
}
void reset(pnode t){
if(t) t->mn = t->mx = t->val;//lazy already propagated
}
void operation(pnode t){//operation of segtree
if(!t) return ;
reset(t) ; // node represents single element of array
propagate(t->l) ; propagate(t->r) ;//imp:propagate lazy before combining l,r
combine(t,t->l,t->r) ; ckmax(t->mx,t->val),ckmin(t->mn,t->val);
}
void split(pnode t,pnode &l,pnode &r,int pos,int add = 0){ // add keeps track of the i value
if(!t){ l = r = NULL ; return ; }
propagate(t) ;
int curr_pos = add + SZ(t->l);
if(curr_pos <= pos){//element at pos goes to "l"
split(t->r, t->r, r, pos, curr_pos+1); l = t;
}else{
split(t->l, l, t->l, pos, add); r = t;
}
upd_sz(t) ; operation(t) ;
}
void merge(pnode &t,pnode l,pnode r){//result/left/right array
propagate(l) ; propagate(r) ;
if(!l or !r){
t = l?l:r;
}else if(l->prior > r->prior) {
merge(l->r,l->r,r); t = l;
}else{
merge(r->l,l,r->l); t = r;
}
upd_sz(t) ; operation(t) ;
}
void insert(int pos,int _val){
pnode r = newnode(pos,_val);
pnode a, b, c;
split(tree, a, b, pos-1) ;
merge(c, a, r);
merge(tree, c, b);
}
void del(int pos){
pnode a, b, c;
split(tree, a, c, pos);
split(a, a, b, pos-1);
merge(tree, a, c);
}
int get(int pos){
pnode a, b, c;
split(tree, a, c, pos) ; split(a, a, b, pos-1) ;
merge(a, a, b) ; merge(tree, a, c) ;
return b->val ;
}
void range_update(int l,int r,int val){ //[l,r]
pnode a, b, c;
split(tree, b, c, r) ; split(b, a, b, l-1) ;
b->lazy += val;
merge(b,a,b) ; merge(tree,b,c) ;
}
int range_query(int l,int r){//[l,r]
pnode a, b, c;
split(tree,a,c,r) ; split(a,a,b,l-1) ;
int ans = max(b->mx,int(-1)*b->mn);
merge(a,a,b) ; merge(tree,a,c) ;
return ans;
}
};
struct compress_1d_co_ordinates {
vector<int> values;
void add(int x){
values.push_back(x);
}
void gen(){
sort(values.begin(),values.end());
values.erase(unique(values.begin(),values.end()),values.end());
}
int get(int x){
int j = lower_bound(values.begin(),values.end(),x) - values.begin();
assert(values[j] == x); return j;
}
}C;
const int LOG = 25;
#undef int
std::vector<int> countScans(std::vector<int> _A,std::vector<int> _X,std::vector<int> _V){
#define int int64_t
setIO() ;
int n = sz(_A), q = sz(_X); //rd(n,q);
vt<int> a;
f(i,0,n) a[i] = _A[i];
for(auto i : a) C.add(i);
vt<pr<int,int>> queries;
f(j,0,q){
int i = _X[j], x = _V[j]; //rd(i,x);
queries.eb(i,x);
C.add(x);
}
C.gen();
for(auto& i : a) i = C.get(i);
for(auto& [i,x]:queries) x = C.get(x);
ordered_set<int> os;
f(i,0,n){
os.insert((a[i]<<int(LOG))+i);
}
IMPLICIT_TREAP treap;
auto position = [&](int i) -> int {
int val = (a[i] << int(LOG)) + i;
return int(os.order_of_key(val));
};
auto add_os = [&](int i) -> void {
int val = (a[i] << int(LOG)) + i;
os.insert(val);
};
auto remove_os = [&](int i) -> void {
int val = (a[i] << int(LOG)) + i;
os.erase(os.find(val));
};
f(i,0,n){
int in = position(i);
treap.insert(in,i - in);
}
vt<int> ans;
for(auto [i,x]:queries){
int in = position(i);
remove_os(i);
a[i] = x;
add_os(i);
int nxt = position(i);
//__f("in,nxt",in,nxt);
if(in < nxt){
treap.insert(nxt+1,i-nxt-1);
treap.del(in);
treap.range_update(in,nxt,1);
}else if(in > nxt){
treap.del(in);
treap.insert(nxt,i-nxt);
treap.range_update(nxt+1,in,-1);
}
ans.pb(treap.range_query(0,n-1));
}
#undef int
vt<int> out(q);
f(i,0,q) out[i] = ans[i];
return out;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
