Задача
Идея строю декартово дерево в вершине храню pos и val изначально pos = {1,2,3,4,5} val = {-1,-1,-1,-1,-1} например если придет какой то запрос типо 2 3 то pos станет pos = {3,1,2,4,5} а val = {2,-1,-1,-1,-1} в конце по всем pos прохожусь и закидываю в массив ans если есть -1 то на шару ставлю еще не использованные числа. И чекаю что бы не было повторении если есть ответ -1 у меня ВА на тесте где должен вывести какой то ответ мой код вывел -1 можете помочь понять что тут не так или мб реализовал я фигово
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define sz size()
#define fill(x, y) memset(x, y, sizeof(x))
const long long INF = 1e18;
const int N = (int)1e6+10;
const int M = (int)2e6+1;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/*
relax
*/
struct node
{
node *l = 0,*r = 0;
ll size,prior,val,pos;
node(int val):size(1),prior(rnd()),val(-1),pos(val){}
};
typedef node *Node;
int size(Node x){
return (x?x->size:0);
}
int val(Node x){
return (x?x->val:-1);
}
void upd(Node x){
if(x){
x -> size = size(x->l)+size(x->r)+1;
}
}
Node merge(Node a,Node b){
if(!a){
return b;
}
if(!b){
return a;
}
if(a -> prior > b->prior){
a -> r = merge(a->r,b);
upd(a);
return a;
}else
{
b ->l = merge(a,b->l);
upd(b);
return b;
}
}
pair<Node,Node> split(Node a,int k)
{
if(!a){
return {0,0};
}
if(size(a->l) >= k){
auto [L,R] = split(a->l,k);
a -> l = R;
upd(a);
return {L,a};
}else{
auto [L,R] = split(a->r,k-size(a->l)-1);
a -> r = L;
upd(a);
return {a,R};
}
}
pair<int,int> get(Node a,int pos){
auto [L,R] = split(a,pos-1);
auto [X,Y] = split(R,1);
pair<int,int> res = {X->pos,val(X)};
a = merge(L,merge(X,Y));
return res;
}
void insert1(Node &a,int i,int val){
Node x = new node(i);
x -> val = val;
a = merge(a,x);
}
void insert(Node &a,int pos,int val){
Node x = new node(pos);
x -> val = val;
a = merge(x,a);
}
void del(Node &a,int pos){
auto [L,R] = split(a,pos-1);
a = merge(L,split(R,1).se);
}
int n,q;
void solve(){
cin >> n >> q;
Node tree = NULL;
for(int i = 1;i <= n;i++){
insert1(tree,i,-1);
}
while(q--)
{
int pos,x;cin >> x >> pos;
pair<int,int> g = get(tree,pos);
int p = g.fi;
del(tree,pos);
insert(tree,p,x);
}
int ans[N];
int cnt[N];
for(int i = 1;i <= n;i++){
pair<int,int> g = get(tree,i);
ans[g.fi] = g.se;
if(g.se!=-1){
cnt[g.se]++;
}
}
vector<int> v;
for(int i = 1;i <= n;i++){
if(!cnt[i])
{
v.pb(i);
}
}
int it = 0;
int b[n+1];
for(int i = 1;i <= n;i++){
if(ans[i]!=-1){
}else{
ans[i] = v[it];
it++;
}
b[i] = ans[i];
}
sort(b+1,b+n+1);
for(int i = 2;i <= n;i++){
if(b[i-1]==b[i]){
cout << -1 << '\n';
return;
}
}
for(int i = 1;i <= n;i++){
cout << ans[i] << ' ';
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int ttt = 1;
//cin >> ttt;
while(ttt--){
solve();
}
}
