Submission #225247

#	Time	Username	Problem	Language	Result	Execution time	Memory
225247		DS007	Robots (IOI13_robots)	C++14	39 / 100	1214 ms	65544 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define lc(v) (v * 2)
#define rc(v) (v * 2 + 1)
#define mid (l + r) / 2
#define ff first
#define ss second

const int N = 1e6;

class seg_tree {
    pair<int, int> t[N * 4];

    void build(int v, int l, int r, pair<int, int> a[]) {
        if (l == r) {
            t[v] = {a[l].ss, a[l].ff};
            return;
        }

        build(lc(v), l, mid, a);
        build(rc(v), mid + 1, r, a);
        t[v] = max(t[lc(v)], t[rc(v)]);
    }

public:
    seg_tree(int n, pair<int, int> a[]) {
        build(1, 0, n - 1, a);
    }

    pair<int, int> query(int v, int l, int r, int tl, int tr) {
        if (tl > tr)
            return {-1, -1};
        else if (l == tl && r == tr)
            return t[v];
        return max(query(lc(v), l, mid, tl, min(mid, tr)), query(rc(v), mid + 1, r, max(tl, mid + 1), tr));
    }

    void update(int v, int l, int r, int tl) {
        if (l == r && l == tl) {
            t[v] = {-1, -1};
            return;
        }

        if (tl <= mid)
            update(lc(v), l, mid, tl);
        else
            update(rc(v), mid + 1, r, tl);
        t[v] = max(t[lc(v)], t[rc(v)]);
    }
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    pair<int, int> t1[T], t2[T];
    multiset<int> x, y;

    for (int i = 0; i < T; i++) {
        t1[i] = {W[i], S[i]};
        t2[i] = {S[i], W[i]};
        x.insert(W[i]);
        y.insert(S[i]);
    }

    sort(t1, t1 + T);
    sort(t2, t2 + T);
    sort(X, X + A);
    sort(Y, Y + B);

    if ((t1[T - 1].ff >= X[A - 1] && t1[T - 1].ss >= Y[B - 1]) || (t2[T - 1].ff >= Y[B - 1] && t2[T - 1].ss >= X[A - 1]))
       return -1;

    multimap<pair<int, int>, int> m1, m2;
    for (int i = 0; i < T; i++) {
        m1.insert({t1[i], i});
        m2.insert({t2[i], i});
    }

    seg_tree st1(T, t1), st2(T, t2);
    int ans = 0, done = 0;

    while (done != T) {
        ans++;
        int p = upper_bound(X, X + A, *x.begin()) - X;
        while (p != A && done != T) {
            pair<int, int> q = st1.query(1, 0, T - 1, 0, lower_bound(t1, t1 + T, pair<int, int>{X[p] - 1, 1e9}) - t1 - 1);
            auto itr = m1.find({q.ss, q.ff});
            st1.update(1, 0, T - 1, itr->ss);
            m1.erase(itr);

            itr = m2.find(q);
            st2.update(1, 0, T - 1, itr->ss);
            m2.erase(itr);

            x.erase(x.find(q.ss));
            y.erase(y.find(q.ff));
            done++;
            int p_ = upper_bound(X, X + A, *x.begin()) - X;
            p = max(p + 1, p_);
        }

        p = upper_bound(Y, Y + B, *y.begin()) - Y;
        while (p != B && done != T) {
            pair<int, int> q = st2.query(1, 0, T - 1, 0, lower_bound(t2, t2 + T, pair<int, int>{Y[p] - 1, 1e9}) - t2 - 1);
            auto itr = m2.find({q.ss, q.ff});
            st2.update(1, 0, T - 1, itr->ss);
            m2.erase(itr);

            itr = m1.find(q);
            st1.update(1, 0, T - 1, itr->ss);
            m1.erase(itr);

            y.erase(y.find(q.ss));
            x.erase(x.find(q.ff));
            done++;
            int p_ = upper_bound(Y, Y + B, *y.begin()) - Y;
            p = max(p + 1, p_);
        }
    }

    return ans;
}

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