Submission #31461

#	Time	Username	Problem	Language	Result	Execution time	Memory
31461		top34051	Robots (IOI13_robots)	C++14	0 / 100	13 ms	65536 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9

struct node {
    int id,x,y;
    node(int _id = 0,int _x = 0,int _y = 0) {
        id = _id; x = _x; y = _y;
    }
};

int n,m,k;
int a[50005], b[50005];
int tree[200005], L[200005], R[200005];
bool ok[1000005];
node px[1000005], py[1000005];
map<int,long long> mp;

bool cmpx(node x,node y) {
    return x.x>y.x;
}

bool cmpy(node x,node y) {
    return x.y>y.y;
}

void build(int* p,int pos,int l,int r,int val) {
    if(l==r) {
        tree[pos] = val;
        L[pos] = R[pos] = p[l];
//        printf("tree [%d, %d] = %d : {%d, %d}\n",l,r,tree[pos],L[pos],R[pos]);
        return ;
    }
    int mid = (l+r)/2;
    build(a,pos<<1,l,mid,val); build(a,pos<<1|1,mid+1,r,val);
    tree[pos] = tree[pos<<1] + tree[pos<<1|1];
    L[pos] = L[pos<<1]; R[pos] = R[pos<<1|1];
//    printf("tree [%d, %d] = %d : {%d, %d}\n",l,r,tree[pos],L[pos],R[pos]);
}

int query(int pos,int l,int r,int val) {
//    printf("query [%d, %d] : %d R = %d\n",l,r,val,R[pos]);
    if(l>r || R[pos]<=val) return inf;
//    printf("!go [%d, %d] : %d\n",l,r,val);
    if(L[pos]>val && tree[pos]>0) return l;
    int mid = (l+r)/2;
    return min(query(pos<<1,l,mid,val), query(pos<<1|1,mid+1,r,val));
}

void update(int pos,int l,int r,int x) {
    if(l>x || r<x) return ;
    if(l==r) {
        tree[pos]--;
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x); update(pos<<1|1,mid+1,r,x);
    tree[pos] = tree[pos<<1] + tree[pos<<1|1];
}

bool check(int cnt) {
    int i,x;
    map<int,long long>::iterator it;
    memset(ok,0,sizeof(ok));
    build(a,1,0,n-1,cnt);
    for(i=0;i<k;i++) {
        x = query(1,0,n-1,py[i].x);
//        printf("1) %d %d => %d\n",py[i].x,py[i].y,x);
        if(x==inf) continue;
        update(1,0,n-1,x);
        ok[py[i].id] = 1;
    }
    build(b,1,0,m-1,cnt);
    for(i=0;i<k;i++) {
        if(ok[px[i].id]) continue;
//        printf("2) %d %d => %d\n",px[i].x,px[i].y,x);
        x = query(1,0,m-1,px[i].y);
        if(x==inf) continue;
        update(1,0,m-1,x);
        ok[px[i].id] = 1;
    }
    for(i=0;i<k;i++) if(!ok[i]) return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int i,l,r,mid,ans;
    n = A; m = B; k = T;
    for(i=0;i<n;i++) a[i] = X[i];
    for(i=0;i<m;i++) b[i] = Y[i];
    for(i=0;i<k;i++) px[i] = py[i] = node(i,W[i],S[i]);
    sort(&px[0],&px[k],cmpx);
    sort(&py[0],&py[k],cmpy);
    sort(&a[0],&a[n]);
    sort(&b[0],&b[m]);
    l = 1; r = k; ans = -1;
    while(l<=r) {
        mid = (l+r)/2;
//        printf("check %d\n",mid);
        if(check(mid)) {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    return ans;
}

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