#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
#define rand() (rand() * rand() + rand() + 1)
struct Node{
int left, right;
int key;
int prior;
int sum, val, ind, lazy;
Node(int k = 0){
left = right = key = prior = sum = val = ind = lazy = 0;
key = k;
}
bool operator<(Node& A){
return key < A.key;
}
bool operator==(Node& A){
return key == A.key;
}
};
vector<Node> node;
namespace Treap{
int root = 0;
int ind = 1;
int new_node(){
return ind++;
}
void push(int j){
if(!j) return;
int l = node[j].left;
int r = node[j].right;
node[j].key += node[j].lazy;
if(l){
node[l].lazy += node[j].lazy;
}
if(r){
node[r].lazy += node[j].lazy;
}
node[j].lazy = 0;
}
void print(int j){
if(!j)return;
push(j);
int l = node[j].left;
int r = node[j].right;
if(l){
print(l);
}
if(r){
print(r);
}
}
void up(int j){
if(!j) return;
int l = node[j].left;
int r = node[j].right;
node[j].sum = node[l].sum + node[r].sum + node[j].val;
}
void split(int j, Node v, int& l, int& r){
push(j);
if(!j) l = r = 0;
else if(node[j] < v){
split(node[j].right, v, node[j].right, r);
l = j;
}
else{
split(node[j].left, v, l, node[j].left);
r = j;
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
void merge(int& j, int l, int r){
push(l);
push(r);
if(!l || !r) j = max(l, r);
else if(node[l].prior > node[r].prior){
merge(node[l].right, node[l].right, r);
j = l;
}
else{
merge(node[r].left, l, node[r].left);
j = r;
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
void insert(int& j, int i){
push(j);
if(!j) j = i;
else if(node[i].prior > node[j].prior){
split(j, node[i], node[i].left, node[i].right);
j = i;
}
else {
if(node[i] < node[j]) insert(node[j].left, i);
else insert(node[j].right, i);
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
int erase(int& j, Node v){
push(j);
if(node[j] == v) {
int ret = j;
merge(j, node[j].left, node[j].right);
return ret;
}
else{
if(v < node[j]) return erase(node[j].left, v);
else return erase(node[j].right, v);
}
push(node[j].left);
push(node[j].right);
up(j);
}
int add(int v, int t, int k){
int j = new_node();
node[j].key = v;
node[j].prior = rand();
node[j].sum = node[j].val = t;
node[j].ind = k;
insert(root, j);
return j;
}
int leftmost(int j){
if(node[j].left) return leftmost(node[j].left);
return j;
}
void update(int j, int v){
int l = 2, r = j;
while(l <= r){
int m = (l + r) / 2;
int tl, tr;
split(root, Node(m), tl, tr);
if(node[tl].sum < v - 1){
l = m + 1;
}
else if(node[tl].sum == v - 1){
root = tl;
add(tr ? node[leftmost(tr)].key : j, v, j);
if(tr) node[tr].lazy++;
merge(root, root, tr);
return;
}
else r = m - 1;
merge(root, tl, tr);
}
node[root].lazy++;
add(1, v, j);
}
void dfs(int j){
push(j);
int l = node[j].left;
int r = node[j].right;
if(l) dfs(l);
if(r) dfs(r);
up(j);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
node = vector<Node> (n + 1);
int last = 0;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
Treap::update(i, x - last);
last = x;
}
Treap::dfs(Treap::root);
for(int i = 1; i <= n; i++) cout << node[i].key << " ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
