Submission #225250

#	Time	Username	Problem	Language	Result	Execution time	Memory
225250		DS007	Robots (IOI13_robots)	C++14	39 / 100	1221 ms	65540 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)]);
        }
    }
};

inline long long cantor(const pair<int, int> &p) {
    return (p.ff + p.ss) * (p.ff + p.ss + 1) / 2 + p.ss;
}

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<long long, int> m1, m2;
    for (int i = 0; i < T; i++) {
        m1.insert({cantor(t1[i]), i});
        m2.insert({cantor(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(0, lower_bound(t1, t1 + T, pair<int, int>{X[p] - 1, 1e9}) - t1);
            auto itr = m1.find(cantor({q.ss, q.ff}));
            st1.update(itr->ss);
            m1.erase(itr);

            itr = m2.find(cantor(q));
            st2.update(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(0, lower_bound(t2, t2 + T, pair<int, int>{Y[p] - 1, 1e9}) - t2);
            auto itr = m2.find(cantor({q.ss, q.ff}));
            st2.update(itr->ss);
            m2.erase(itr);

            itr = m1.find(cantor(q));
            st1.update(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