This is about this problem on spoj, which I reached from the CP algo treap page.
My code passes upto around testcase #15 but then gives WA.
This being my first problem I actually coded treaps on, I most probably have made clumsy errors, but in the 30 min of checking I did I see no obvious error.
Can anyone help?
Here is my code:
#include <bits/stdc++.h>
using namespace std;
struct node{
int key;
int priority;
node* left;
node* right;
//int size;
int id;
int lazy;
};
node* newNode(int key, int id){
node* n = new node;
n->left = n->right = NULL;
n->key = key;
n->id = id;
n->lazy = 0;
n->priority = rand();
return n;
}
//Splits treap into < X and > X treaps in O(log n) time
void split(node* n, int key, node* &l, node* &r){
//Splits the treap at node n, and fills l and r with
//resultant treaps
if(n){
//if(key == 5) cout << n->id << endl;
if(n->left) n->left->lazy += n->lazy;
if(n->right) n->right->lazy += n->lazy;
n->key += n->lazy;
n->lazy = 0;
}
if(!n) l = r = NULL; //No treap
else if(key <= n->key){
//traverse left
split(n->left,key,l,n->left); //Split and rejoin unused part of left with >X key
r = n;
}
else{
split(n->right,key,n->right,r);
l = n;
}
/*if(l){
l->size = 1;
if(l->left) l->size += l->left->size;
if(l->right) l->size += l->right->size;
}
if(r){
r->size = 1;
if(r->left) r->size += r->right->size;
if(r->right) r->size += r->right->size;
}*/
}
//Inserts a node into treap in O(log n) time
void insert(node* &n, node* in){
if(n){
if(n->left) n->left->lazy += n->lazy;
if(n->right) n->right->lazy += n->lazy;
n->key += n->lazy;
n->lazy = 0;
}
if(!n) n = in;
else if(in->priority > n->priority){
split(n,in->key,in->left,in->right);
n = in;
if(n->right) n->right->lazy++;
}
else{
if(in->key <= n->key){
n->key++;
if(n->right) n->right->lazy++;
insert(n->left,in);
}
else
insert(n->right,in);
}
}
void dfs(node* &n, int arr[]){
if(!n) return;
if(n->left) n->left->lazy += n->lazy;
if(n->right) n->right->lazy += n->lazy;
n->key += n->lazy;
n->lazy = 0;
arr[n->id] = n->key;
dfs(n->left, arr);
dfs(n->right, arr);
}
/*
void dfs2(node* &n){
if(!n){cout << "nuLL" << endl; return;}
if(n->left) n->left->lazy += n->lazy;
if(n->right) n->right->lazy += n->lazy;
n->key += n->lazy;
n->lazy = 0;
//arr[n->id] = n->key;
cout << n->id << ' ' << n->key << endl;
dfs2(n->left);
dfs2(n->right);
}
*/
void solve(int iter){
int N;
cin >> N;
int height[N];
node *root = NULL;
bool possible = true;
int temp;
for(int i = 0; i < N; i++){
cin >> temp;
if(temp > i){
possible = false;
break;
}
insert(root,newNode(i-temp+1,i));
//dfs2(root);
//cout << "----" << endl;
}
cout << "Test : " << iter << endl;
if(!possible) cout << -1 << endl;
else{
dfs(root,height);
for(int i = 0; i < N; i++)
cout << height[i] << ' ';
cout << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
for(int i = 1; i <= T; i++)
solve(i);
return 0;
}
I’m basically using treaps with lazy update (IDK if there is any such term as ‘lazy’ as in the case of segtree but thats what I came up with).
Thanks.