oj.uz

Submission #602132

# Submission time Handle Problem Language Result Execution time Memory
602132 2022-07-22T15:27:58 Z DJeniUp Sweeping (JOI20_sweeping) C++17
10 / 100
 13288 ms 1345808 KB 
#include <bits/stdc++.h>

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'

ll n,m,q,h;

struct D{
    ll u,r,x,y,s[2],gx,gy;
}l;

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

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

vector<D>d;

vector<vector<ll> >v[2];


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 AddF(ll r,ll x,ll y,ll tp){
    for(int i=x;i>0;i-=(i&-i)){
        v[tp][r][i]=max(v[tp][r][i],y);
    }
    return ;
}

ll R(ll r,ll tp,ll x){
    ll res=0;
    for(int i=x;i<v[tp][r].size();i+=(i&-i)){
        res=max(res,v[tp][r][i]);
    }
    return res;
}


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){
    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].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;
        }
        return {m1.fr,x};
    }
}

ll M(ll x,ll y,ll tp,ll r){
    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].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;
        }
        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;
        }
        return y;
    }
}

void Adddek(ll x,ll r,ll tp,ll num){
    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=rand();
    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;
    root[tp][r]=M(M(m1.fr,sz[tp][r],tp,r),m1.sc,tp,r);
    sz[tp][r]++;
    return ;

}

ll Deldek(ll x,ll vnum,ll tp,ll r){
    if(x==-1)return -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;
        }
        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;
        }
    }else{
        tr[tp][r][x].r=Deldek(tr[tp][r][x].r,vnum+1,tp,r);
        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;
        }
    }
    return x;
}

void Del(ll x,ll tp,ll r){
    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);
    widlozhene.clear();
    return ;
}

void Update(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;
    }
    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 ;
    }

    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);
    if(t[z].x+t[z].y>n)exit(1);
    Add(t[z].x,t[z].y,z,t[z].r);
    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);
    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);
    Add(t[z].x,t[z].y,z,t[z].r);
    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);
    return ;
}


void Newy(ll r){
    if(d[r].u==-1){
        h++;
        d.pb(l);
        v[0].pb(v1);
        v[1].pb(v1);
        v[0][h].pb(0);
        v[1][h].pb(0);
        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;
        d[h].s[0]=1;
        d[h].s[1]=1;
        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);
        v[0].pb(v1);
        v[1].pb(v1);
        v[0][h].pb(0);
        v[1][h].pb(0);
        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;
        d[h].s[0]=1;
        d[h].s[1]=1;
        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){
    while(d[r].x<x || d[r].y<y){
        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].s[0]=d[r].s[0];
    t[num].s[1]=d[r].s[1];
    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;
            Perekinuvy(m1.fr,y,0,r);
            Newy(r);
            r=d[r].u;
        }else{
            Update(root[1][r],y,1,r);
            v[1][r].pb(0);
            AddF(r,d[r].s[1],y,1);
            d[r].s[1]++;
            Newx(r);
            r=d[r].r;
        }
    }
    Update(root[1][r],y,1,r);
    v[1][r].pb(0);
    AddF(r,d[r].s[1],y,1);
    d[r].s[1]++;
    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;
            Perekinuvx(m1.fr,x,1,r);
            Newx(r);
            r=d[r].r;
        }else{
            Update(root[0][r],x,0,r);
            v[0][r].pb(0);
            AddF(r,d[r].s[0],x,0);
            d[r].s[0]++;
            Newy(r);
            r=d[r].u;
        }
    }
    Update(root[0][r],x,0,r);
    v[0][r].pb(0);
    AddF(r,d[r].s[0],x,0);
    d[r].s[0]++;
    return ;
}

int main()
{
    cin>>n>>m>>q;
    d.pb(l);
    v[0].pb(v1);
    v[1].pb(v1);
    v[0][0].pb(0);
    v[1][0].pb(0);
    d[0].u=-1;
    d[0].r=-1;
    d[0].y=n/2;
    d[0].x=n-d[0].y;
    d[0].s[0]=1;
    d[0].s[1]=1;
    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;
            Addx(n-x,x);
        }else if(t1==3){
            ll x;
            cin>>x;
            Addy(x,n-x);
        }else{
            ll x;
            cin>>x;
            t[x].y=max(t[x].y,R(t[x].r,1,t[x].s[1]));
            t[x].x=max(t[x].x,R(t[x].r,0,t[x].s[0]));
            Del(t[x].numdek,0,t[x].r);
            Del(t[x].numdek,1,t[x].r);
            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 R(ll, ll, ll)':
sweeping.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=x;i<v[tp][r].size();i+=(i&-i)){
      |                 ~^~~~~~~~~~~~~~~~
sweeping.cpp: In function 'll Deldek(ll, ll, ll, ll)':
sweeping.cpp:149:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     if(vnum+1==widlozhene.size()){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp: In function 'void Addy(ll, ll)':
sweeping.cpp:330:16: warning: unused variable 'mx' [-Wunused-variable]
  330 |             ll mx=0;
      |                ^~
sweeping.cpp: In function 'void Addx(ll, ll)':
sweeping.cpp:358:16: warning: unused variable 'mx' [-Wunused-variable]
  358 |             ll mx=0;
      |                ^~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6252 KB Output is correct
2 Runtime error 1 ms 468 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8572 ms 1345808 KB Output is correct
2 Correct 8782 ms 1319836 KB Output is correct
3 Correct 8741 ms 1319884 KB Output is correct
4 Correct 8426 ms 984812 KB Output is correct
5 Correct 13288 ms 1325220 KB Output is correct
6 Correct 11405 ms 1244724 KB Output is correct
7 Correct 11937 ms 1262704 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 842 ms 63104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 842 ms 63104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6252 KB Output is correct
2 Runtime error 1 ms 468 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -