Submission #70357

#	Time	Username	Problem	Language	Result	Execution time	Memory
70357		MANcity	Robots (IOI13_robots)	C++14	76 / 100	1546 ms	65176 KiB

robots

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "robots.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int T;
pair<LL,pair<LL,int> > Sx[1000010];
pair<LL,pair<LL,int> > Sy[1000010];
int posx[1000010];
int posy[1000010];
pair<LL,int> tx[5*1000002];
pair<LL,int> ty[5*1000002];
void update_x(int left,int right,int pos,int v,LL val)
{
    if(left==right)
        tx[v]=mp(val,left);
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update_x(left,m,pos,2*v,val);
        else
            update_x(m+1,right,pos,2*v+1,val);
        tx[v]=max(tx[2*v],tx[2*v+1]);
    }
}
pair<LL,int> getmax_x(int left,int right,int l,int r,int v)
{
    if(l>r)
        return {-1,-1};
    if(left==l && right==r)
        return tx[v];
    int m=(left+right)/2;
    pair<LL,int> A=getmax_x(left,m,l,min(r,m),2*v);
    pair<LL,int> B=getmax_x(m+1,right,max(l,m+1),r,2*v+1);
    return max(A,B);
}
void update_y(int left,int right,int pos,int v,LL val)
{
    if(left==right)
        ty[v]=mp(val,left);
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update_y(left,m,pos,2*v,val);
        else
            update_y(m+1,right,pos,2*v+1,val);
        ty[v]=max(ty[2*v],ty[2*v+1]);
    }
}
pair<LL,int> getmax_y(int left,int right,int l,int r,int v)
{
    if(l>r)
        return {-1,-1};
    if(left==l && right==r)
        return ty[v];
    int m=(left+right)/2;
    pair<LL,int> A=getmax_y(left,m,l,min(r,m),2*v);
    pair<LL,int> B=getmax_y(m+1,right,max(l,m+1),r,2*v+1);
    return max(A,B);
}
int bin_x(LL VAL)
{
    int l=0;
    int r=T-1;
    while(1)
    {
        if(l==r)
            return l;
        int m=(l+r+1)/2;
        if(Sx[m].first<VAL)
            l=m;
        else
            r=(m-1);
    }
}
int bin_y(LL VAL)
{
    int l=0;
    int r=T-1;
    while(1)
    {
        if(l==r)
            return l;
        int m=(l+r+1)/2;
        if(Sy[m].first<VAL)
            l=m;
        else
            r=(m-1);
    }
}
int putaway(int A, int B, int T_0, int X[], int Y[], int W[], int S[]) {
    T=T_0;
    for0(i,T-1)
        Sx[i]={W[i],{S[i],i}};
    for0(i,T-1)
        Sy[i]={S[i],{W[i],i}};
    sort(Sx,Sx+T);
    sort(Sy,Sy+T);
    for0(i,T-1)
        update_x(0,T-1,i,1,Sx[i].second.first);
    for0(i,T-1)
    {
        update_y(0,T-1,i,1,Sy[i].second.first);
    }
    for0(i,T-1)
    {
        posx[Sx[i].second.second]=i;
        posy[Sy[i].second.second]=i;
    }
    sort(X,X+A);
    sort(Y,Y+B);
    LL Time=0;
    int qan=0;
    /*for0(i,T-1)
        cout<<Sx[i].first<<" ";
    cout<<endl;
    for0(i,T-1)
        cout<<Sx[i].second.first<<" ";
    cout<<endl;
    cout<<endl;
    for0(i,T-1)
        cout<<Sy[i].first<<" ";
    cout<<endl;
    for0(i,T-1)
        cout<<Sy[i].second.first<<" ";
    cout<<endl;
    cout<<endl;*/
    while(1)
    {
        int u=0;
        for0(i,A-1)
        {
            if(Sx[0].first<X[i])
            {
                int myx=bin_x(X[i]);
                pair<LL,int> max_bef=getmax_x(0,T-1,0,myx,1);
                if(max_bef.first>0)
                {
                    u=1;
                    qan++;
                    int pos_bef=max_bef.second;
                    update_x(0,T-1,pos_bef,1,-1);
                    int pos_y=Sx[pos_bef].second.second;
                    update_y(0,T-1,posy[pos_y],1,-1);
                }
            }
        }
        for0(i,B-1)
        {
            if(Sy[0].first<Y[i])
            {
                int myy=bin_y(Y[i]);
                pair<LL,int> max_bef=getmax_y(0,T-1,0,myy,1);
                if(max_bef.first>0)
                {
                    u=1;
                    qan++;
                    int pos_bef=max_bef.second;
                    update_y(0,T-1,pos_bef,1,-1);
                    int pos_x=Sy[pos_bef].second.second;
                    update_x(0,T-1,posx[pos_x],1,-1);
                }
            }
        }
        /*cout<<endl;
        cout<<endl;
        int r;
        cin>>r;*/
        if(u==0)
            return (-1);
        Time++;
        if(qan==T)
            return Time;
    }
}
/*

*/

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