Submission #261465

#	Time	Username	Problem	Language	Result	Execution time	Memory
261465		Sorting	Tram (CEOI13_tram)	C++17	10 / 100	54 ms	5868 KiB

tram

#include <bits/stdc++.h>

using namespace std;

const int k_N = 15e4 + 3;
const int k_M = 3e4 + 3;
const long long k_Inf = 1.1e18;

int n, m;

pair<int, int> p[k_M];
int p_cnt = 0;

struct Node{
    long long len;
    int x, y;

    Node(){}
    Node(long long len, int x, int y):len(len), x(x), y(y){}

    friend bool operator<(const Node &lvalue, const Node &rvalue){
        if(lvalue.len != rvalue.len) return lvalue.len > rvalue.len;
        if(lvalue.x != rvalue.x) return lvalue.x < rvalue.x;
        return lvalue.y < rvalue.y;
    }
};

set<pair<int,int>> pos;
set<Node> s;

Node get_node_1(pair<int, int> t){
    //cout << t.first << " " << t.second << " t" << "\n";
    assert(t.second == 1 || t.second == 2);
    return {1, t.first, 3 - t.second};
}

Node get_node_2(pair<long long, int> l, pair<long long, int> r){
    auto [lf, ls] = l;
    auto [rf, rs] = r;

    if(lf + 1 == rf) return {0, -1, -1};
    if(lf == 0){
        if(rs == 1) return {(rf - 1) * (rf - 1) + 1, 1, 2};
        else if(rs == 2) return {(rf - 1) * (rf - 1) + 1, 1, 1};
        else return {(rf - 1) * (rf - 1), 1, 1};
    }
    if(rf == n + 1){
        if(ls == 1) return {(n - lf) * (n - lf) + 1, n, 2};
        else if(ls == 2) return {(n - lf) * (n - lf) + 1, n, 1};
        else return {(n - lf) * (n - lf), n, 1};
    }

    int mid = (rf + lf) / 2;
    if((rf - lf) % 2 == 0){
        if((ls | rs) == 3) return {(rf - mid) * (rf - mid), mid, 1};
        else if(ls == 2) return {(rf - mid) * (rf - mid) + 1, mid, 1};
        else return {(rf - mid) * (rf - mid) + 1, mid, 2};
    }
    else{
        if(ls != 3) return {(mid - lf) * (mid - lf) + 1, mid, (3 - ls)};
        else if(rs != 3) return {(rf - (mid + 1)) * (rf - (mid + 1)) + 1, mid, (3 - rs)};
        else return {(mid - lf) * (mid - lf), mid, 1};
    }
}

pair<int, int> add(){
    Node nd = *s.begin();
    s.erase(nd);

    //cout << "nd - " << nd.x << " " << nd.y << "\n";

    auto it = pos.find({nd.x, 3 - nd.y});
    if(it != pos.end()){
        it--;
        auto prev = *it;
        it++;
        auto curr = *it;
        it++;
        auto nxt = *it;
        it--;

        pos.erase(curr);
        s.erase(get_node_2(prev, curr));
        s.erase(get_node_2(curr, nxt));

        pair<int, int> new_curr = {nd.x, 3};
        
        pos.insert(new_curr); 
        s.insert(get_node_2(prev, new_curr));
        s.insert(get_node_2(new_curr, nxt));
    }
    else{
        auto it = pos.insert({nd.x, nd.y}).first;
        pair<int, int> curr = *it;

        it--;
        auto prev = *it;
        it++, it++;
        auto nxt = *it;

        s.erase(get_node_2(prev, nxt));

        s.insert(get_node_2(prev, curr));
        s.insert(get_node_2(curr, nxt));
        s.insert(get_node_1(curr));
    }

    return {nd.x, nd.y};
}

void remove(pair<int, int> place){
    //cout << "remove " << place.first << " " << place.second << "\n";

    auto it = pos.find(place);
    if(it == pos.end()){
        it = pos.find({place.first, 3});
        
        it--;
        auto prev = *it;
        it++;
        auto curr = *it;
        it++;
        auto nxt = *it;

        pos.erase({place.first, 3});
        pos.insert({place.first, 3 - place.second});
        pair<int, int> new_curr = {place.first, 3 - place.second};

        s.erase(get_node_2(prev, curr));
        s.erase(get_node_2(curr, nxt));
        
        s.insert(get_node_2(prev, new_curr));
        s.insert(get_node_2(new_curr, nxt));
        s.insert(get_node_1(new_curr));
    }
    else{
        it--;
        auto prev = *it;
        it++;
        auto curr = *it;
        it++;
        auto nxt = *it;

        //cout << "prev: " << prev.first << " " << prev.second << "\n";
        //cout << "curr: " << curr.first << " " << curr.second << "\n";
        //cout << "nxt: " << nxt.first << " " << nxt.second << "\n";

        pos.erase(curr);

        s.erase(get_node_2(prev, curr));
        s.erase(get_node_2(curr, nxt));
        s.erase(get_node_1(curr));

        s.insert(get_node_2(prev, nxt));
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    pos.insert({0, 3});
    pos.insert({n + 1, 3});

    s.insert(get_node_2({0, 3}, {n + 1, 3}));

    for(int i = 1; i <= m; ++i){
        char type;
        cin >> type;

        if(type == 'E'){
            p[i] = add();
            cout << p[i].first << " " << p[i].second << "\n";
        }
        else{
            int idx;
            cin >> idx;
            remove(p[idx]);
        }

        /*cout << "\ns:\n";
        for(auto &t: s)
            cout << t.len << " - " << t.x << " " << t.y << "\n";
        
        cout << "\npos\n";
        for(auto &t: pos)
            cout << t.first << " " << t.second << "\n";
        cout <<"\n";*/
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20