#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
#define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0;}
#else
#define debug(x...)
#define light_debug(x)
#endif
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(0, 1 << 30);
class Treap{
private:
struct node{
int v, i, prior, size, diff, dp;
node* l; node* r;
node(int _v, int _i){
prior = uid(rng);
v = _v;
i = _i;
dp = i;
l = r = 0;
size = 1;
}
};
using pnode = node*;
pnode root = 0;
inline int size(pnode t){
return t ? t->size : 0;
}
inline int dp(pnode t){
return t ? t->dp : 0;
}
inline void pull(pnode t){
if(t) {
t->size = size(t->l) + 1 + size(t->r);
t->dp = max(max(dp(t->l), dp(t->r) - size(t->l) - 1), t->i - size(t->l));
}
}
void split(pnode t, pnode& l, pnode& r, int v, int i){
if(!t)
l = r = 0;
else if(make_pair(t->v, t->i) <= make_pair(v, i))
split(t->r, t->r, r, v, i), l = t;
else
split(t->l, l, t->l, v, i), r = t;
pull(t);
}
void merge(pnode& t, pnode l, pnode r){
if(!l || !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;
pull(t);
}
public:
void insert(int i, int v){
pnode l, m, r;
split(root, m, r, v, i);
split(m, l, m, v, i - 1);
m = new node(v, i);
merge(root, l, m);
merge(root, root, r);
}
void erase(int i, int v){
pnode l, m, r;
split(root, m, r, v, i);
split(m, l, m, v, i - 1);
m = 0;
merge(root, l, m);
merge(root, root, r);
}
int query(){
return root->dp;
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int N = A.size(), Q = X.size();
Treap trp;
vector<int> answer(Q);
rep(i, N)
trp.insert(i, A[i]);
rep(i, Q){
int x = X[i], v = V[i];
trp.erase(x, A[x]);
trp.insert(x, v);
A[x] = v;
cout << trp.query() << '\n';
}
return answer;
}
signed main1(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int N, Q;
Treap trp;
vi A;
cin >> N >> Q;
A.resize(N);
rep(i, N) {
cin >> A[i];
trp.insert(i, A[i]);
}
debug(trp.query());
while(Q--){
int x, v;
cin >> x >> v;
trp.erase(x, A[x]);
trp.insert(x, v);
A[x] = v;
cout << trp.query() << '\n';
}
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
2048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
