Submission #587391

#	Time	Username	Problem	Language	Result	Execution time	Memory
587391		AlperenT	Robots (IOI13_robots)	C++17	76 / 100	1529 ms	65536 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

const int N = 1e6 + 5e4 + 5;

int ans = 0;

map<int, int> cmprsx, cmprsy;
multiset<int> curx, cury, curw, curs;
vector<int> used;

struct SegTree{
    int tree[N * 4];
    multiset<pair<int, int>> st;

    int getmax(int l){
        auto it = st.upper_bound({l, N});

        if(it == st.begin() || prev(it)->first != l) return 0;
        else return prev(it)->second; 
    }

    int merge(int a, int b){
        if(getmax(a) > getmax(b)) return a;
        else return b;
    }

    void build(int v = 1, int l = 1, int r = N - 1){
        if(l == r) tree[v] = l;
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m);
            build(v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    void update(int pos, int v = 1, int l = 1, int r = N - 1){
        if(l == r) tree[v] = l;
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, v * 2, l, m);
            else update(pos, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    int query(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
        if(l > r) return 0;
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
        }
    }
};

SegTree wsgt, ssgt;

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
    for(int i = 0; i < a; i++) cmprsx[x[i]] = 1;
    for(int i = 0; i < b; i++) cmprsy[y[i]] = 1;

    for(int i = 0; i < t; i++) cmprsx[w[i]] = cmprsy[s[i]] = 1;

    int tmp = 0;

    for(auto &p : cmprsx) p.second = ++tmp;

    tmp = 0;

    for(auto &p : cmprsy) p.second = ++tmp;

    for(int i = 0; i < a; i++) x[i] = cmprsx[x[i]];
    for(int i = 0; i < b; i++) y[i] = cmprsy[y[i]];

    for(int i = 0; i < t; i++) w[i] = cmprsx[w[i]], s[i] = cmprsy[s[i]];

    sort(x, x + a);
    sort(y, y + b);

    for(int i = 0; i < a; i++) curx.insert(x[i]);
    for(int i = 0; i < b; i++) cury.insert(y[i]);
    for(int i = 0; i < t; i++) curw.insert(w[i]), curs.insert(s[i]);

    for(int i = 0; i < t; i++) wsgt.st.insert({w[i], s[i]});
    for(int i = 0; i < t; i++) ssgt.st.insert({s[i], w[i]});

    wsgt.build();
    ssgt.build();

    while(curw.size()){
        bool flag = false;
        ans++;

        used.clear();

        while(!curw.empty() && !curx.empty()){
            int ww = *curw.begin();

            auto it = curx.upper_bound(ww);

            if(it == curx.end()) break;

            int xx = *it;

            curx.erase(it);

            used.push_back(xx);

            int p = wsgt.query(1, xx - 1);

            curw.erase(curw.find(p));
            curs.erase(curs.find(wsgt.getmax(p)));

            ssgt.st.erase(ssgt.st.find({wsgt.getmax(p), p}));
            ssgt.update(wsgt.getmax(p));

            wsgt.st.erase(wsgt.st.find({p, wsgt.getmax(p)}));
            wsgt.update(p);

            flag = true;
        }

        for(auto xx : used) curx.insert(xx);

        used.clear();

        while(!curs.empty() && !cury.empty()){
            int ss = *curs.begin();

            auto it = cury.upper_bound(ss);

            if(it == cury.end()) break;

            int yy = *it;

            cury.erase(it);

            used.push_back(yy);

            int p = ssgt.query(1, yy - 1);

            curs.erase(curs.find(p));
            curw.erase(curw.find(ssgt.getmax(p)));

            wsgt.st.erase(wsgt.st.find({ssgt.getmax(p), p}));
            wsgt.update(ssgt.getmax(p));

            ssgt.st.erase(ssgt.st.find({p, ssgt.getmax(p)}));
            ssgt.update(p);

            flag = true;
        }

        for(auto yy : used) cury.insert(yy);

        if(flag == false) return -1;
    }

    return ans;
}

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