oj.uz

Submission #602283

# Submission time Handle Problem Language Result Execution time Memory
602283 2022-07-22T20:42:03 Z DJeniUp Sweeping (JOI20_sweeping) C++17
100 / 100
 15311 ms 1817072 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,X,Y;

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){
   //// 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=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;
   // 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;
        }
        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();
    //cout<<x<<endl;
    //cout<<"!";
    while(x!=-1){
        //cout<<x<<" ";
        widlozhene.pb(x);
        x=tr[tp][r][x].par;
    }
    //cout<<endl;
    //cout<<"#";
    reverse(widlozhene.begin(),widlozhene.end());
    if(widlozhene[0]!=root[tp][r])exit(1);
    //cout<<"&";
    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);
    //if(t[z].y>Y)exit(1);
    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);
        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){
    //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].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;
            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);
            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;
            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);
            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;
            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;
            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<<"? ";
            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:175:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     if(vnum+1==widlozhene.size()){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp: In function 'void Addy(ll, ll)':
sweeping.cpp:379:16: warning: unused variable 'mx' [-Wunused-variable]
  379 |             ll mx=0;
      |                ^~
sweeping.cpp: In function 'void Addx(ll, ll)':
sweeping.cpp:408:16: warning: unused variable 'mx' [-Wunused-variable]
  408 |             ll mx=0;
      |                ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6252 KB Output is correct
2 Correct 23 ms 8516 KB Output is correct
3 Correct 19 ms 1088 KB Output is correct
4 Correct 29 ms 6248 KB Output is correct
5 Correct 19 ms 1900 KB Output is correct
6 Correct 14 ms 932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8200 ms 1345900 KB Output is correct
2 Correct 8128 ms 1321396 KB Output is correct
3 Correct 8440 ms 1321640 KB Output is correct
4 Correct 9309 ms 984816 KB Output is correct
5 Correct 15311 ms 1328848 KB Output is correct
6 Correct 11279 ms 1248980 KB Output is correct
7 Correct 8089 ms 1264220 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11018 ms 1500724 KB Output is correct
2 Correct 10683 ms 1528508 KB Output is correct
3 Correct 6005 ms 1207000 KB Output is correct
4 Correct 11048 ms 1444120 KB Output is correct
5 Correct 10558 ms 1415408 KB Output is correct
6 Correct 9515 ms 1361760 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 11018 ms 1500724 KB Output is correct
2 Correct 10683 ms 1528508 KB Output is correct
3 Correct 6005 ms 1207000 KB Output is correct
4 Correct 11048 ms 1444120 KB Output is correct
5 Correct 10558 ms 1415408 KB Output is correct
6 Correct 9515 ms 1361760 KB Output is correct
7 Correct 9305 ms 1490400 KB Output is correct
8 Correct 12496 ms 1487200 KB Output is correct
9 Correct 8897 ms 1488228 KB Output is correct
10 Correct 9173 ms 1203496 KB Output is correct
11 Correct 12706 ms 1380524 KB Output is correct
12 Correct 13355 ms 1420856 KB Output is correct
13 Correct 13425 ms 1389520 KB Output is correct
14 Correct 318 ms 8228 KB Output is correct
15 Correct 9689 ms 162304 KB Output is correct
16 Correct 8471 ms 1396020 KB Output is correct
17 Correct 11555 ms 1405248 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6252 KB Output is correct
2 Correct 23 ms 8516 KB Output is correct
3 Correct 19 ms 1088 KB Output is correct
4 Correct 29 ms 6248 KB Output is correct
5 Correct 19 ms 1900 KB Output is correct
6 Correct 14 ms 932 KB Output is correct
7 Correct 8200 ms 1345900 KB Output is correct
8 Correct 8128 ms 1321396 KB Output is correct
9 Correct 8440 ms 1321640 KB Output is correct
10 Correct 9309 ms 984816 KB Output is correct
11 Correct 15311 ms 1328848 KB Output is correct
12 Correct 11279 ms 1248980 KB Output is correct
13 Correct 8089 ms 1264220 KB Output is correct
14 Correct 11018 ms 1500724 KB Output is correct
15 Correct 10683 ms 1528508 KB Output is correct
16 Correct 6005 ms 1207000 KB Output is correct
17 Correct 11048 ms 1444120 KB Output is correct
18 Correct 10558 ms 1415408 KB Output is correct
19 Correct 9515 ms 1361760 KB Output is correct
20 Correct 9305 ms 1490400 KB Output is correct
21 Correct 12496 ms 1487200 KB Output is correct
22 Correct 8897 ms 1488228 KB Output is correct
23 Correct 9173 ms 1203496 KB Output is correct
24 Correct 12706 ms 1380524 KB Output is correct
25 Correct 13355 ms 1420856 KB Output is correct
26 Correct 13425 ms 1389520 KB Output is correct
27 Correct 318 ms 8228 KB Output is correct
28 Correct 9689 ms 162304 KB Output is correct
29 Correct 8471 ms 1396020 KB Output is correct
30 Correct 11555 ms 1405248 KB Output is correct
31 Correct 6727 ms 693772 KB Output is correct
32 Correct 8417 ms 1353684 KB Output is correct
33 Correct 6815 ms 1817072 KB Output is correct
34 Correct 8685 ms 1426616 KB Output is correct
35 Correct 8538 ms 1427208 KB Output is correct
36 Correct 8299 ms 1032740 KB Output is correct
37 Correct 14629 ms 1352968 KB Output is correct
38 Correct 14039 ms 1271836 KB Output is correct
39 Correct 11700 ms 1201488 KB Output is correct
40 Correct 8148 ms 1271120 KB Output is correct