Submission #259985

#	Time	Username	Problem	Language	Result	Execution time	Memory
259985		eohomegrownapps	Robots (IOI13_robots)	C++14	0 / 100	1 ms	384 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll w,h;

//map<ll,int> grid;
int indices[1000000];
ll dp[2][50001];
//ll m = 1e9;
int vals[1000000];
int xcs[1000000];
int ycs[1000000];
int vtot=0;

int *xc, *yc;
int n;

int ns;

int nc=0;

ll gcd2(ll a, ll b){
    return a+b;
}

struct NodeY{
    int s,e;
    ll v;
    NodeY *l = NULL;
    NodeY *r = NULL;
    NodeY(int _s, int _e){
        nc++;
        s=_s;e=_e;
        v=0;
    }

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeY(s,(s+e)/2);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeY((s+e)/2+1,e);
    }

    ll getL(){
        if (l==NULL){
            return 0;
        }
        return l->v; 
    }

    ll getR(){
        if (r==NULL){
            return 0;
        }
        return r->v;
    }

    void update(int ind, ll val){
        //cout<<"y "<<s<<' '<<e<<'\n';
        //cout<<"u "<<ind<<' '<<val<<'\n';
        if (s==e){
            v=val;
            return;
        }
        if (ind<=(s+e)/2){
            makeL();
            l->update(ind,val);
        } else {
            makeR();
            r->update(ind,val);
        }
        v=gcd2(getL(),getR());
    }

    ll queryL(int ya, int yb){
        if (l==NULL){
            return 0;
        }
        return l->query(ya,yb);
    }

    ll queryR(int ya, int yb){
        if (r==NULL){
            return 0;
        }
        return r->query(ya,yb);
    }

    ll query(int ya, int yb){
        if (s==ya&&e==yb){
            return v;
        }
        int m = (s+e)/2;
        if (yb<=m){
            return queryL(ya,yb);
        } else if (m<ya){
            return queryR(ya,yb);
        } else {
            return gcd2(queryL(ya,m),queryR(m+1,yb));
        }
    }

    void combine(NodeY *lc, NodeY *rc, int ind){
        //cout<<s<<' '<<e<<' '<<"com\n";
        int m = (s+e)/2;
        if (s==e){
            v=gcd2((lc==NULL)?0:lc->v,(rc==NULL)?0:rc->v);
            return;
        }
        if (lc==NULL&&rc==NULL){
            v=0;
            return;
        }
        if (ind<=m){
            makeL();
            l->combine((lc==NULL)?(NodeY*)NULL:lc->l,(rc==NULL)?(NodeY*)NULL:rc->l,ind);
        } else {
            makeR();
            r->combine((lc==NULL)?(NodeY*)NULL:lc->r,(rc==NULL)?(NodeY*)NULL:rc->r,ind);
        }
        v=gcd2((l==NULL)?0:l->v,(r==NULL)?0:r->v);
    }
};

struct NodeX{
    int s,e;
    NodeY *v;
    NodeX *l = NULL;
    NodeX *r = NULL;
    NodeX(int _s, int _e){
        nc++;
        s=_s;e=_e;
        v=new NodeY(0,ns-1);
    }

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeX(s,(s+e)/2);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeX((s+e)/2+1,e);
    }

    void update(int indx, int indy, ll val){
        //cout<<"x "<<s<<' '<<e<<'\n';
        //cout<<"u "<<indx<<' '<<indy<<' '<<val<<'\n';
        if (s==e){
            v->update(indy,val);
            return;
        }
        if (indx<=(s+e)/2){
            makeL();
            l->update(indx,indy,val);
        } else {
            makeR();
            r->update(indx,indy,val);
        }
        //cout<<"combine\n";
        v->combine((l==NULL)?(NodeY*)NULL:l->v,(r==NULL)?(NodeY*)NULL:r->v,indy); //???
    }

    ll queryL(int xa, int xb, int ya, int yb){
        if (l==NULL){
            return 0;
        }
        return l->query(xa,xb,ya,yb);
    }

    ll queryR(int xa, int xb, int ya, int yb){
        if (r==NULL){
            return 0;
        }
        return r->query(xa,xb,ya,yb);
    }

    ll query(int xa, int xb, int ya, int yb){
        int m = (s+e)/2;
        assert(xa<=xb&&ya<=yb);
        if (s==xa&&e==xb){
            return v->query(ya,yb);
        }
        if (xb<=m){
            return queryL(xa,xb,ya,yb);
        } else if (m<xa){
            return queryR(xa,xb,ya,yb);
        } else {
            return gcd2(queryL(xa,m,ya,yb),queryR(m+1,xb,ya,yb));
        }
    }
};

NodeX *root;

bool success(ll mid){
    ns=h;
    root = new NodeX(0,w-1);
    /*for (int y = 0; y<2; y++){
        for (int x = 0; x<=w; x++){
            dp[y][x]=0;
        }
    }
    for (ll i = w-1; i>=0; i--){
        dp[0][i]=mid*(w-1-i);
    }*/
    /*bool c = 1;
    int cnt = 0;
    for (ll y = h-1; y>=0; y--){
        dp[c][w]=mid*(h-1-y);
        for (ll x = w-1; x>=0; x--){
            dp[c][x]=dp[c][x+1]+dp[!c][x]-dp[!c][x+1];//-grid[x*m+y];
            while (cnt<vtot&&xcs[cnt]==x&&ycs[cnt]==y){
                dp[c][x]-=vals[cnt];
                cnt++;
            }
            if (dp[c][x]<0){
                return false;
            }
        }
        c=!c;
    }*/
    for (int cnt = 0; cnt<vtot; cnt++){
        ll val = root->query(xcs[cnt],w-1,ycs[cnt],h-1);
        ll tot = mid*(h-1-ycs[cnt]+w-1-xcs[cnt]);
        if (tot-val-vals[cnt]<0){
            return false;
        }
        root->update(xcs[cnt],ycs[cnt],vals[cnt]);
    }
    return true;
}

bool comp(int a, int b){
    if (yc[a]==yc[b]){
        return xc[a]>xc[b];
    } else {
        return yc[a]>yc[b];
    }
}

int putaway(int lx, int ly, int N, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
    n=N;
    sort(xpos,xpos+lx);
    sort(ypos,ypos+ly);
    for (ll i = 0; i<n; i++){
        xtoys[i]=upper_bound(xpos,xpos+lx,xtoys[i])-xpos;
        ytoys[i]=upper_bound(ypos,ypos+ly,ytoys[i])-ypos;
    }
    w=lx+1;
    h=ly+1;
    xc=xtoys;yc=ytoys;
    //grid.resize(w,vector<ll>(h,0));
    /*for (ll i = 0; i<n; i++){
        grid[(xtoys[i])*m+ytoys[i]]++;
    }

    if (grid[(w-1)*m+h-1]>0){
        return -1;
    }*/
    for (int i = 0; i<n; i++){
        indices[i]=i;
    }
    sort(indices,indices+n,comp);
    int curx = xtoys[indices[0]];
    int cury = ytoys[indices[0]];
    int cnt = 0;
    for (int i = 0; i<n; i++){
        if (xtoys[indices[i]]==curx&&xtoys[indices[i]]==cury){
            cnt++;
        } else {
            xcs[vtot]=curx;
            ycs[vtot]=cury;
            vals[vtot]=cnt;
            curx=xtoys[indices[i]];
            cury=ytoys[indices[i]];
            vtot++;
            cnt=1;
        }
    }
    if (cnt>0){
        xcs[vtot]=curx;
        ycs[vtot]=cury;
        vals[vtot]=cnt;
        vtot++;
    }
    /*for (int i = 0; i<n; i++){
        cout<<xtoys[indices[i]]<<' '<<ytoys[indices[i]]<<'\n';
    }*/
    if (xtoys[indices[0]]==w-1&&ytoys[indices[0]]==h-1){
        return -1;
    }
    /*for (int i = 0; i<xcs.size(); i++){
        cout<<xcs[i]<<' '<<ytoys[i]<<' '<<vals[i]<<'\n';
    }*/
    ll l = 0, r = n;
    while (l<=r){
        ll mid = (l+r)/2;;
        if (success(mid)){
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:318:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10