Submission #748002

#	Time	Username	Problem	Language	Result	Execution time	Memory
748002		ETheBest3	Robots (IOI13_robots)	C++14	39 / 100	282 ms	16928 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define lli int
using namespace std;
const lli MAXN=1000005, INF=999999999;
lli tree[4*MAXN], pl[MAXN], br, now;
bool used[MAXN];
struct rob{
    lli w, s, ind;
    const bool operator <(rob p){
        if(s!=p.s)return s>p.s;
        if(w!=p.w)return w>p.w;
        return ind<p.ind;
    }
};
rob a[MAXN];
void build_tree(lli ind, lli l, lli r){
    if(l==r){
        tree[ind]=a[l].w;
        return;
    }
    lli mid=(l+r)/2;
    build_tree(2*ind, l, mid);
    build_tree(2*ind+1, mid+1, r);
    tree[ind]=min(tree[2*ind], tree[2*ind+1]);
    return;
}
void update(lli ind, lli l, lli r, lli q, lli d){
    if(l>q or r<q)return;
    if(l==r){
        tree[ind]=d;
        used[l]=1;
        return;
    }
    lli mid=(l+r)/2;
    update(2*ind, l, mid, q, d);
    update(2*ind+1, mid+1, r, q, d);
    tree[ind]=min(tree[2*ind], tree[2*ind+1]);
    return;
}
int query(lli ind, lli l, lli r, lli q){
    if(l==r)return l;
    lli mid=(l+r)/2;
    if(tree[2*ind]<q)return query(2*ind, l, mid, q);
    return query(2*ind+1, mid+1, r, q);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(lli i=0; i<T; i++){
        a[i]={W[i], S[i], i};
    }
    sort(a, a+T);
    sort(X, X+A);
    sort(Y, Y+B);
    for(lli i=0; i<T; i++){
        pl[a[i].ind]=i;
    }
    build_tree(1, 0, T-1);
    if(T%(A+B)==0)br=T/(A+B);
    else br=(T/(A+B))+1;
    for(lli i=0; i<A; i++){
        lli t=0;
        while(t<br){
            lli ind=query(1, 0, T-1, X[i]);
            if(a[ind].w>=X[i])break;
            update(1, 0, T-1, ind, INF);
            t++;
        }
        now+=t;
        if(i==A-1 and B==0)break;
        if((T-now)%(A+B-i-1)==0)br=max(br, (T-now)/(A+B-i-1));
        else br=max(br, (T-now)/(A+B-i-1)+1);
    }
    lli p1=T-1;
    for(lli i=0; i<B; i++){
        lli t=0;
        while(t<br){
            while(used[p1]==1 and p1>=0)p1--;
            if(p1<0 or a[p1].s>=Y[i])break;
            p1--;
            t++;
        }
        now+=t;
        if(i==B-1)break;
        if((T-now)%(B-i-1)==0)br=max(br, (T-now)/(B-i-1));
        else br=max(br, (T-now)/(B-i-1)+1);
    }
    while(used[p1]==1 and p1>=0)p1--;
    if(p1>=0)return -1;
    return br;
}

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