oj.uz

Submission #107172

# Submission time Handle Problem Language Result Execution time Memory
107172 2019-04-22T09:32:28 Z naoai Tram (CEOI13_tram) C++14
100 / 100
 316 ms 16408 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 620 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 11 ms 620 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 620 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 7 ms 620 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1388 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 8 ms 876 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1388 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 8 ms 876 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 3048 KB Output is correct
2 Correct 124 ms 1112 KB Output is correct
3 Correct 147 ms 3052 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 16408 KB Output is correct
2 Correct 99 ms 1004 KB Output is correct
3 Correct 221 ms 5100 KB Output is correct