oj.uz

Submission #602304

# Submission time Handle Problem Language Result Execution time Memory
602304 2022-07-22T21:12:42 Z DJeniUp Sweeping (JOI20_sweeping) C++17
100 / 100
 12421 ms 888032 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000007
#define N 100000
#define endl '\n'

mt19937 rnd(time(nullptr));

ll n,m,q,h,X,Y;

struct D{
    ll u,r,x,y,gx,gy;
}l;

struct T{
    ll x,y,r,num,u[2],numdek;
}t[1500007];

struct Tree{
    ll l,r,prom,key,mx,h,par,num;
}tre;

vector<D>d;

vector<vector<Tree> >tr[2];

set<pairlll>k,k1,ps;
vector<ll>v1,root[2],sz[2],widlozhene;
set<ll>u1;
vector<Tree> tree;


void Push(ll x,ll y,ll tp,ll r){
    if(x==-1)return ;
    tr[tp][r][x].h=y;
    tr[tp][r][x].prom=y;
    tr[tp][r][x].mx=y;
    return ;
}

pairll S(ll x,ll y,ll tp,ll r){
   //// cout<<x<<" "<<y<<" "<<tp<<" "<<r<<endl;
    ////cout<<"S"<<endl;
    if(x==-1)return {-1,-1};
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }
    tr[tp][r][x].par=-1;
    if(tr[tp][r][x].h<=y){
        pairll m1=S(tr[tp][r][x].r,y,tp,r);
        tr[tp][r][x].r=m1.fr;
        if(tr[tp][r][x].l!=-1){
            tr[tp][r][tr[tp][r][x].l].par=x;
        }
        if(tr[tp][r][x].r!=-1){
            tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
            tr[tp][r][tr[tp][r][x].r].par=x;
        }else{
            tr[tp][r][x].mx=tr[tp][r][x].h;
        }
        return {x,m1.sc};
    }else{
        pairll m1=S(tr[tp][r][x].l,y,tp,r);
        tr[tp][r][x].l=m1.sc;
        if(tr[tp][r][x].l!=-1){
            tr[tp][r][tr[tp][r][x].l].par=x;
        }
        if(tr[tp][r][x].r!=-1){
            tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
            tr[tp][r][tr[tp][r][x].r].par=x;
        }else{
            tr[tp][r][x].mx=tr[tp][r][x].h;
        }
        return {m1.fr,x};
    }
}

ll M(ll x,ll y,ll tp,ll r){
   // cout<<x<<" "<<y<<" "<<tp<<" "<<r<<" "<<endl;
    if(x==-1)return y;
    if(y==-1)return x;
    tr[tp][r][x].par=-1;
    tr[tp][r][y].par=-1;
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }
    if(tr[tp][r][y].prom!=0){
        Push(tr[tp][r][y].l,tr[tp][r][y].prom,tp,r);
        Push(tr[tp][r][y].r,tr[tp][r][y].prom,tp,r);
        tr[tp][r][y].prom=0;
    }
    if(tr[tp][r][x].key>tr[tp][r][y].key){

        tr[tp][r][x].r=M(tr[tp][r][x].r,y,tp,r);
        if(tr[tp][r][x].l!=-1){
            tr[tp][r][tr[tp][r][x].l].par=x;
        }
        if(tr[tp][r][x].r!=-1){
            tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
            tr[tp][r][tr[tp][r][x].r].par=x;
        }else{
            tr[tp][r][x].mx=tr[tp][r][x].h;
        }
        return x;
    }else{

        tr[tp][r][y].l=M(x,tr[tp][r][y].l,tp,r);
        if(tr[tp][r][y].l!=-1){
            tr[tp][r][tr[tp][r][y].l].par=y;
        }
        if(tr[tp][r][y].r!=-1){
            tr[tp][r][y].mx=max(tr[tp][r][y].h,tr[tp][r][tr[tp][r][y].r].mx);
            tr[tp][r][tr[tp][r][y].r].par=y;
        }else{
            tr[tp][r][y].mx=tr[tp][r][y].h;
        }
        return y;
    }
}

void Adddek(ll x,ll r,ll tp,ll num){
    //cout<<"!"<<endl;
    pairll m1=S(root[tp][r],x,tp,r);
    t[num].numdek=sz[tp][r];
    tr[tp][r].pb(tre);
    tr[tp][r][sz[tp][r]].l=-1;
    tr[tp][r][sz[tp][r]].r=-1;
    tr[tp][r][sz[tp][r]].key=rnd();
    tr[tp][r][sz[tp][r]].mx=x;
    tr[tp][r][sz[tp][r]].h=x;
    tr[tp][r][sz[tp][r]].par=-1;
    tr[tp][r][sz[tp][r]].num=num;
   // cout<<"!"<<endl;
    root[tp][r]=M(M(m1.fr,sz[tp][r],tp,r),m1.sc,tp,r);
    if(root[tp][r]!=-1)tr[tp][r][root[tp][r]].par=-1;
    sz[tp][r]++;
    return ;

}

ll Deldek(ll x,ll vnum,ll tp,ll r){
    if(x==-1)return -1;
    //if(widlozhene[vnum]!=x)exit(1);
    if(vnum+1==widlozhene.size()){
        tr[tp][r][x].par=-1;
        if(tr[tp][r][x].prom!=0){
            Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
            Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
            tr[tp][r][x].prom=0;
        }
        if(tp==0)t[tr[tp][r][x].num].x=max(t[tr[tp][r][x].num].x,tr[tp][r][x].h);
        if(tp==1)t[tr[tp][r][x].num].y=max(t[tr[tp][r][x].num].y,tr[tp][r][x].h);
        return M(tr[tp][r][x].l,tr[tp][r][x].r,tp,r);
    }
    tr[tp][r][x].par=-1;
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }
    if(widlozhene[vnum+1]==tr[tp][r][x].l){
        tr[tp][r][x].l=Deldek(tr[tp][r][x].l,vnum+1,tp,r);
        if(tr[tp][r][x].l!=-1){
            tr[tp][r][tr[tp][r][x].l].par=x;
        }
        if(tr[tp][r][x].r!=-1){
            tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
            tr[tp][r][tr[tp][r][x].r].par=x;
        }else{
            tr[tp][r][x].mx=tr[tp][r][x].h;
        }
    }else{
        tr[tp][r][x].r=Deldek(tr[tp][r][x].r,vnum+1,tp,r);
        if(tr[tp][r][x].l!=-1){
            tr[tp][r][tr[tp][r][x].l].par=x;
        }
        if(tr[tp][r][x].r!=-1){
            tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
            tr[tp][r][tr[tp][r][x].r].par=x;
        }else{
            tr[tp][r][x].mx=tr[tp][r][x].h;
        }
    }
    return x;
}

void Del(ll x,ll tp,ll r){
    widlozhene.clear();
    while(x!=-1){
        widlozhene.pb(x);
        x=tr[tp][r][x].par;
    }
    reverse(widlozhene.begin(),widlozhene.end());
    root[tp][r]=Deldek(root[tp][r],0,tp,r);
    if(root[tp][r]!=-1)tr[tp][r][root[tp][r]].par=-1;
    widlozhene.clear();
    return ;
}

void Update(ll x,ll y,ll tp,ll r){
    if(x==-1)return ;

    if(tr[tp][r][x].mx<=y){
        tr[tp][r][x].mx=y;
        tr[tp][r][x].h=y;
        tr[tp][r][x].prom=y;
        return ;
    }
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }

    Update(tr[tp][r][x].l,y,tp,r);
    if(tr[tp][r][x].h<y){
        tr[tp][r][x].h=y;
        tr[tp][r][x].mx=max(y,tr[tp][r][x].mx);
        Update(tr[tp][r][x].r,y,tp,r);
    }
    return ;

}

void Add(ll x,ll y,ll num,ll r);

void Perekinuvy(ll x,ll y,ll tp,ll r){
    if(x==-1)return ;
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }
    ll z=tr[tp][r][x].num;
    t[z].x=max(t[z].x,tr[tp][r][x].h);
    t[z].y=max(t[z].y,y);
    Perekinuvy(tr[tp][r][x].l,y,tp,r);
    Perekinuvy(tr[tp][r][x].r,y,tp,r);
    Del(t[z].numdek,1,t[z].r);
    Add(t[z].x,t[z].y,z,t[z].r);
    return ;
}

void Perekinuvx(ll x,ll y,ll tp,ll r){
    if(x==-1)return ;
    if(tr[tp][r][x].prom!=0){
        Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
        Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
        tr[tp][r][x].prom=0;
    }
    ll z=tr[tp][r][x].num;
    t[z].y=max(t[z].y,tr[tp][r][x].h);
    t[z].x=max(t[z].x,y);
    Perekinuvx(tr[tp][r][x].l,y,tp,r);
    Perekinuvx(tr[tp][r][x].r,y,tp,r);
    Del(t[z].numdek,0,t[z].r);
    Add(t[z].x,t[z].y,z,t[z].r);
    return ;
}


void Newy(ll r){
    if(d[r].u==-1){
        h++;
        d.pb(l);
        d[r].u=h;
        d[h].u=-1;
        d[h].r=-1;
        d[h].x=(d[r].x+d[r].gx)/2;
        d[h].y=n-d[h].x;
        d[h].gx=d[r].gx;
        d[h].gy=d[r].y;
        tr[0].pb(tree);
        tr[1].pb(tree);
        root[0].pb(-1);
        root[1].pb(-1);
        sz[0].pb(0);
        sz[1].pb(0);
    }
    return ;
}
void Newx(ll r){
    if(d[r].r==-1){
        h++;
        d.pb(l);
        d[r].r=h;
        d[h].r=-1;
        d[h].u=-1;
        d[h].y=(d[r].y+d[r].gy)/2;
        d[h].x=n-d[h].y;
        d[h].gy=d[r].gy;
        d[h].gx=d[r].x;
        tr[0].pb(tree);
        tr[1].pb(tree);
        root[0].pb(-1);
        root[1].pb(-1);
        sz[0].pb(0);
        sz[1].pb(0);
    }
    return ;
}

void Add(ll x,ll y,ll num,ll r){
    //cout<<x<<" "<<y<<endl;
    while(d[r].x<x || d[r].y<y){
        //cout<<r<<" "<<d[r].x<<" "<<d[r].y<<endl;
        if(x+y>n)exit(0);
        if(d[r].y<y){
            Newy(r);
            r=d[r].u;
        }else{
            Newx(r);
            r=d[r].r;
        }
    }

    t[num].r=r;
    Adddek(x,r,0,num);
    Adddek(y,r,1,num);
    return ;
}

void Addy(ll x,ll y){
    ll r=0;
    while(d[r].x<x || d[r].y<y){
        if(d[r].y<y){

            ll mx=0;
            pairll m1=S(root[0][r],x,0,r);
            root[0][r]=m1.sc;
            if(root[0][r]!=-1)tr[0][r][root[0][r]].par=-1;
            Perekinuvy(m1.fr,y,0,r);
            Newy(r);
            r=d[r].u;
        }else{
            Update(root[1][r],y,1,r);
            Newx(r);
            r=d[r].r;
        }
    }
    Update(root[1][r],y,1,r);
    return ;
}

///////
void Addx(ll x,ll y){
    ll r=0;
    while(d[r].x<x || d[r].y<y){
        if(d[r].x<x){

            ll mx=0;
            pairll m1=S(root[1][r],y,1,r);
            root[1][r]=m1.sc;
            if(root[1][r]!=-1)tr[1][r][root[1][r]].par=-1;
            Perekinuvx(m1.fr,x,1,r);
            Newx(r);
            r=d[r].r;
        }else{
            Update(root[0][r],x,0,r);
            Newy(r);
            r=d[r].u;
        }
    }
    Update(root[0][r],x,0,r);
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    d.pb(l);
    d[0].u=-1;
    d[0].r=-1;
    d[0].y=n/2;
    d[0].x=n-d[0].y;
    tr[0].pb(tree);
    tr[1].pb(tree);
    root[0].pb(-1);
    root[1].pb(-1);
    sz[0].pb(0);
    sz[1].pb(0);
    for(int i=1;i<=m;i++){
        cin>>t[i].x>>t[i].y;
        t[i].num=i;
        Add(t[i].x,t[i].y,i,0);
    }

    for(int i=1;i<=q;i++){
        ll t1;
        cin>>t1;
        if(t1==4){
            m++;
            cin>>t[m].x>>t[m].y;
            t[m].num=m;
            Add(t[m].x,t[m].y,m,0);
        }else if(t1==2){
            ll x;
            cin>>x;
            X=n-x;
            Y=x;
            Addx(n-x,x);
        }else if(t1==3){
            ll x;
            cin>>x;
            X=x;
            Y=n-x;
            Addy(x,n-x);
        }else{
            ll x;
            cin>>x;
            Del(t[x].numdek,0,t[x].r);
            Del(t[x].numdek,1,t[x].r);
            //cout<<"? ";
            cout<<t[x].x<<" "<<t[x].y<<endl;
            Add(t[x].x,t[x].y,x,t[x].r);
        }
    }


    return 0;
}

Compilation message

sweeping.cpp: In function 'll Deldek(ll, ll, ll, ll)':
sweeping.cpp:163:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     if(vnum+1==widlozhene.size()){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp: In function 'void Addy(ll, ll)':
sweeping.cpp:347:16: warning: unused variable 'mx' [-Wunused-variable]
  347 |             ll mx=0;
      |                ^~
sweeping.cpp: In function 'void Addx(ll, ll)':
sweeping.cpp:370:16: warning: unused variable 'mx' [-Wunused-variable]
  370 |             ll mx=0;
      |                ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3816 KB Output is correct
2 Correct 9 ms 4532 KB Output is correct
3 Correct 11 ms 1192 KB Output is correct
4 Correct 16 ms 3648 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Correct 8 ms 952 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5037 ms 739208 KB Output is correct
2 Correct 5030 ms 711900 KB Output is correct
3 Correct 4874 ms 711492 KB Output is correct
4 Correct 6269 ms 498328 KB Output is correct
5 Correct 12158 ms 841052 KB Output is correct
6 Correct 8427 ms 748264 KB Output is correct
7 Correct 4825 ms 687732 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6885 ms 857016 KB Output is correct
2 Correct 7611 ms 888032 KB Output is correct
3 Correct 3257 ms 626480 KB Output is correct
4 Correct 7962 ms 873568 KB Output is correct
5 Correct 7580 ms 847804 KB Output is correct
6 Correct 6293 ms 780212 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6885 ms 857016 KB Output is correct
2 Correct 7611 ms 888032 KB Output is correct
3 Correct 3257 ms 626480 KB Output is correct
4 Correct 7962 ms 873568 KB Output is correct
5 Correct 7580 ms 847804 KB Output is correct
6 Correct 6293 ms 780212 KB Output is correct
7 Correct 5324 ms 778368 KB Output is correct
8 Correct 5332 ms 773608 KB Output is correct
9 Correct 5294 ms 779088 KB Output is correct
10 Correct 5512 ms 623936 KB Output is correct
11 Correct 8962 ms 812108 KB Output is correct
12 Correct 10413 ms 843628 KB Output is correct
13 Correct 10026 ms 822740 KB Output is correct
14 Correct 122 ms 4176 KB Output is correct
15 Correct 7672 ms 156808 KB Output is correct
16 Correct 4899 ms 730648 KB Output is correct
17 Correct 5003 ms 724776 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3816 KB Output is correct
2 Correct 9 ms 4532 KB Output is correct
3 Correct 11 ms 1192 KB Output is correct
4 Correct 16 ms 3648 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Correct 8 ms 952 KB Output is correct
7 Correct 5037 ms 739208 KB Output is correct
8 Correct 5030 ms 711900 KB Output is correct
9 Correct 4874 ms 711492 KB Output is correct
10 Correct 6269 ms 498328 KB Output is correct
11 Correct 12158 ms 841052 KB Output is correct
12 Correct 8427 ms 748264 KB Output is correct
13 Correct 4825 ms 687732 KB Output is correct
14 Correct 6885 ms 857016 KB Output is correct
15 Correct 7611 ms 888032 KB Output is correct
16 Correct 3257 ms 626480 KB Output is correct
17 Correct 7962 ms 873568 KB Output is correct
18 Correct 7580 ms 847804 KB Output is correct
19 Correct 6293 ms 780212 KB Output is correct
20 Correct 5324 ms 778368 KB Output is correct
21 Correct 5332 ms 773608 KB Output is correct
22 Correct 5294 ms 779088 KB Output is correct
23 Correct 5512 ms 623936 KB Output is correct
24 Correct 8962 ms 812108 KB Output is correct
25 Correct 10413 ms 843628 KB Output is correct
26 Correct 10026 ms 822740 KB Output is correct
27 Correct 122 ms 4176 KB Output is correct
28 Correct 7672 ms 156808 KB Output is correct
29 Correct 4899 ms 730648 KB Output is correct
30 Correct 5003 ms 724776 KB Output is correct
31 Correct 4436 ms 425572 KB Output is correct
32 Correct 5254 ms 735292 KB Output is correct
33 Correct 2981 ms 828920 KB Output is correct
34 Correct 5775 ms 760424 KB Output is correct
35 Correct 5623 ms 760476 KB Output is correct
36 Correct 6101 ms 517304 KB Output is correct
37 Correct 12421 ms 823852 KB Output is correct
38 Correct 10779 ms 752000 KB Output is correct
39 Correct 9229 ms 690100 KB Output is correct
40 Correct 5102 ms 675576 KB Output is correct