Submission #107172

#	Time	Username	Problem	Language	Result	Execution time	Memory
107172		naoai	Tram (CEOI13_tram)	C++14	100 / 100	316 ms	16408 KiB

tram

#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin ("x.in"); ofstream fout ("x.out");

typedef long long i64;

const int nmax = 15e4 + 5;
const int mmax = 3e4 + 5;
const i64 inf = 1LL << 60;

struct str {
    int x, y;
    i64 d;

    str () {}
    str (int _x, int _y, i64 _d) {
        x = _x, y = _y, d = _d;
    }

    bool operator < (const str &shp) const {
        if (d != shp.d) return d > shp.d;
        if (x != shp.x) return x < shp.x;
        return y < shp.y;
    }
};

int n;
set<str> s1; // permanent am si lin 1, n
multiset<int> s2;

bool busy[nmax + 1][2];
pair<int, int> loc[mmax + 1];

i64 cost (int x, int y) {
    if (busy[x][y])
        return 0;

    i64 ans = inf;

    if (busy[x][1 - y]) ans = 1;

    multiset<int>::iterator it = s2.lower_bound(x);

    if (it != s2.begin()) {
        -- it;

        int l = *it;
        for (int i = 0; i < 2; ++ i) {
            if (busy[l][i] == 1) {
                ans = min(ans, 1LL * (x - l) * (x - l) + abs(y - i));
            }
        }
    }

    it = s2.upper_bound(x);
    if (it != s2.end()) {
        int l = *it;

        for (int i = 0; i < 2; ++ i) {
            if (busy[l][i] == 1)
                ans = min(ans, 1LL * (x - l) * (x - l) + abs(y - i));
        }
    }

    return ans;
}

void add (int a, int b) {
    int mij = (a + b) / 2;

    for (int i = -1; i <= 1; ++ i) {
        int x = mij + i;

        if (x < 1 || x > n) continue;

        for (int j = 0; j < 2; ++ j) {
            if (busy[x][j]) continue;

            s1.insert(str(x, j, cost(x, j)));
        }
    }
}

void update (int x) {
    if (s2.find(x) != s2.end()) {
        multiset<int>::iterator it = s2.upper_bound(x);
        if (it != s2.end()) // x si urmatoarea
            add(x, *it);

        it = s2.lower_bound(x);
        if (it != s2.begin()) { // x si anterioara
            -- it;
            add(*it, x);
        }
    } else {
        multiset<int>::iterator it1 = s2.upper_bound(x), it2;
        it2 = it1;

        if (it1 != s2.begin() && it1 != s2.end()) {
            -- it2;
            add(*it2, *it1);
        }
    }

    if (!busy[1][0]) s1.insert(str(1, 0, cost(1, 0)));
    if (!busy[1][1]) s1.insert(str(1, 1, cost(1, 1)));

    if (n > 1) {
        if (!busy[n][0]) s1.insert(str(n, 0, cost(n, 0)));
        if (!busy[n][1]) s1.insert(str(n, 1, cost(n, 1)));
    }
}

int main () {
    int m;
    fin >> n >> m;

    s1.insert(str(1, 0, cost(1, 0)));
    s1.insert(str(1, 1, cost(1, 1)));

    if (n > 1) {
        s1.insert(str(n, 0, cost(n, 0)));
        s1.insert(str(n, 1, cost(n, 1)));
    }

    for (int i = 1; i <= m; ++ i) {
        char ch;

        fin >> ch;

        if (ch == 'E') {
            while (!s1.empty() && cost(s1.begin() -> x, s1.begin() -> y) != s1.begin() -> d) {
                s1.erase(s1.begin());
            }

            assert(!s1.empty());

            int x = s1.begin() -> x, y = s1.begin() -> y;
            s1.erase(s1.begin());

            busy[x][y] = 1;
            loc[i] = {x, y};
            fout << x << " " << y + 1 << "\n";

            s2.insert(x);
            update(x);
        } else {
            int u;
            fin >> u;
            int x = loc[u].first, y = loc[u].second;

          // fout << "-" << x << " " << y + 1 << "\n";
            busy[x][y] = 0;
            s2.erase(s2.find(x));
            update(x);
        }
    }
    return 0;
}

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