Submission #587402

#	Time	Username	Problem	Language	Result	Execution time	Memory
587402		AlperenT	Robots (IOI13_robots)	C++17	0 / 100	3040 ms	62680 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;
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;

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]];

    cmprsx.clear(); cmprsy.clear();

    for(int i = 0; i < a; i++) curx.insert(x[i]);

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

    wsgt.build();

    while(!wsgt.st.empty()){
        bool flag = false;
        ans++;
        used.clear();

        while(!wsgt.st.empty() && !curx.empty()){
            int ww = wsgt.st.begin()->first;

            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);

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

            flag = true;
        }

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

        used.clear();

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

    return ans;
}

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