Submission #98832

#	Time	Username	Problem	Language	Result	Execution time	Memory
98832		Alexa2001	Robots (IOI13_robots)	C++17	100 / 100	2309 ms	26616 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;
typedef long long ll;

const int Nmax = 50005, Mmax = 1e6 + 5;

int x[Mmax], y[Mmax], lim1, lim2;
vector<int> v[Nmax];


int cbin(int a[], int n, int x)
{
    int st = 0, dr = n - 1;
    while(st <= dr)
        if(a[mid] > x) st = mid+1;
            else dr = mid-1;

    return dr + 1;
}

class SegTree
{
    ll a[Nmax<<2]; int lazy[Nmax<<2];
public:
    void build(int node, int st, int dr, int val)
    {
        lazy[node] = 0;
        if(st == dr)
        {
            a[node] = - (ll) st * val;
            return;
        }
        build(left_son, st, mid, val);
        build(right_son, mid+1, dr, val);
        a[node] = max(a[left_son], a[right_son]);
    }

    void update(int node, int st, int dr, int L)
    {
        if(L <= st)
        {
            lazy[node] ++;
            return;
        }

        if(L <= mid) update(left_son, st, mid, L);
        update(right_son, mid+1, dr, L);

        a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
    }

    ll query()
    {
        return a[1] + lazy[1];
    }

} aint;


bool check(int D)
{
    aint.build(1, 0, lim2, D);
    int i;
    for(i=0; i<=lim1; ++i)
    {
        for(auto it : v[i]) aint.update(1, 0, lim2, it);
        if((ll) D * i < aint.query()) return 0;
    }
    return 1;
}

int putaway(int A, int B, int N, int W[], int S[], int X[], int Y[])
{
    int i;
    sort(W, W+A); reverse(W, W+A);
    sort(S, S+B); reverse(S, S+B);

    for(i=0; i<N; ++i)
    {
        x[i] = cbin(W, A, X[i]);
        y[i] = cbin(S, B, Y[i]);

        if(x[i] == 0 && y[i] == 0) return -1;
    }

    for(i=0; i<N; ++i)
        v[x[i]].push_back(y[i]);

    lim1 = A; lim2 = B;

    int st = 0, dr = N;
    while(st <= dr)
        if(check(mid)) dr = mid - 1;
            else st = mid+1;
    return st;
}

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