Submission #225826

#	Time	Username	Problem	Language	Result	Execution time	Memory
225826		DS007	Robots (IOI13_robots)	C++14	39 / 100	567 ms	37456 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;
    int n;

    void build(int v, int l, int r, pair<int, int> a[]) {
        for (int i = 0; i < n; i++)
            t[n + i] = {a[i].ss, a[i].ff};

        for (int i = n - 1; i >= 1; i--)
            t[i] = max(t[lc(i)], t[rc(i)]);
    }

public:
    seg_tree(int n, pair<int, int> a[]) {
        this->n = n;
        t = new pair<int, int>[n * 2];
        build(1, 0, n - 1, a);
    }

    pair<int, int> query(int l, int r) {
        l += n;
        r += n;
        pair<int, int> mi = {-1, -1};

        while (l < r) {
            if (l & 1)
                mi = max(mi, t[l]), l++;
            if (r & 1)
                r--, mi = max(mi, t[r]);
            l /= 2, r /= 2;
        }

        return mi;
    }

    void update(int pos) {
        pos += n;
        t[pos] = {-1, -1};

        while (pos > 1) {
            pos >>= 1;
            t[pos] = max(t[lc(pos)], t[rc(pos)]);
        }
    }
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    pair<int, int> t1[T], t2[T];
    priority_queue<int, vector<int>, decltype(greater<>())> x, y, x_, y_;

    for (int i = 0; i < T; i++) {
        t1[i] = {W[i], S[i]};
        t2[i] = {S[i], W[i]};
        x.push(W[i]);
        y.push(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;

    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.top()) - X;
        while (p != A && done != T) {
            pair<int, int> q = st1.query(0, lower_bound(t1, t1 + T, pair<int, int>{X[p] - 1, 1e9}) - t1);
            int ind = upper_bound(t1, t1 + T, pair<int, int>{q.ss, q.ff}) - t1 - 1;
            t1[ind].ss = 1e9 + 7;
            st1.update(ind);
            x_.push(q.ss);

            ind = upper_bound(t2, t2 + T, q) - t2 - 1;
            t2[ind].ss = 1e9 + 7;
            st2.update(ind);
            y_.push(q.ff);

            while (!x_.empty() && x.top() == x_.top())
                x.pop(), x_.pop();
            while (!y_.empty() && y.top() == y_.top())
                y.pop(), y_.pop();

            done++;
            int p_ = upper_bound(X, X + A, x.top()) - X;
            p = max(p + 1, p_);
        }

        p = upper_bound(Y, Y + B, y.top()) - Y;
        while (p != B && done != T) {
            pair<int, int> q = st2.query(0, lower_bound(t2, t2 + T, pair<int, int>{Y[p] - 1, 1e9}) - t2);
            int ind = upper_bound(t2, t2 + T, pair<int, int>{q.ss, q.ff}) - t2 - 1;
            t2[ind].ss = 2e9 + 7;
            st2.update(ind);
            y_.push(q.ss);

            ind = upper_bound(t1, t1 + T, q) - t1 - 1;
            t1[ind].ss = 2e9 + 7;
            st1.update(ind);
            x_.push(q.ff);

            while (!x_.empty() && x.top() == x_.top())
                x.pop(), x_.pop();
            while (!y_.empty() && y.top() == y_.top())
                y.pop(), y_.pop();

            done++;
            int p_ = upper_bound(Y, Y + B, y.top()) - 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