oj.uz

Submission #270560

# Submission time Handle Problem Language Result Execution time Memory
270560 2020-08-17T18:17:47 Z johutha Tram (CEOI13_tram) C++17
65 / 100
 47 ms 3808 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <memory>

#define int long long

using namespace std;

signed main()
{
    iostream::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    set<int> rws;
    vector<bool> tram(2*n);

    auto getdist = [&](int ps)
    {
        int rw = ps / 2;
        if (tram[ps] == 1) return 0ll;
        if (tram[2*rw] || tram[2*rw + 1]) return 2ll;

        auto nxp = rws.upper_bound(rw);
        int bf = -1;
        int nx = -1;
        if (nxp != rws.end()) nx = *nxp;
        if (nxp != rws.begin()) bf = *prev(nxp);

        int dst = 1e9;
        if (bf != -1) dst = min(dst, 2*(rw - bf) + 1 - (tram[2*bf + (ps % 2)]));
        if (nx != -1) dst = min(dst, 2*(nx - rw) + 1 - (tram[2*nx + (ps % 2)]));
        return dst;
    };

    priority_queue<pair<int,int>> pq;
    vector<int> pass(q);

    auto addrw = [&](int rw)
    {
        if (!tram[2*rw]) pq.push({getdist(2*rw), -2*rw});
        if (!tram[2*rw + 1]) pq.push({getdist(2*rw + 1), -(2*rw + 1)});
    };

    auto add = [&](int rw)
    {
        addrw(rw);
        auto nxp = rws.upper_bound(rw);
        int nx = n - 1;
        int mn = n - 1;
        if (nxp != rws.end()) { nx = (*nxp + rw) / 2; mn = *nxp; }
        int pr = 0;
        
        nxp = rws.lower_bound(rw);
        if (nxp != rws.begin()) { pr = (*prev(nxp) + rw) / 2; mn += *prev(nxp); }

        if (rws.count(rw) == 0) addrw(mn / 2);
        if (rw < nx) addrw(nx);
        if (pr < rw) addrw(pr);
    };

    for (int cq = 0; cq < q; cq++)
    {
        char m;
        cin >> m;
        if (m == 'E')
        {
            int lc = -1;
            while (!pq.empty() && lc == -1)
            {
                int ds, cn;
                tie(ds, cn) = pq.top();
                pq.pop();
                cn = -cn;
                if (getdist(cn) == ds) lc = cn;
            }
            if (lc == -1) lc = 0;
            pass[cq] = lc;
            tram[lc] = true;
            cout << (lc / 2) + 1 << " " << (lc % 2) + 1 << "\n";
            int rw = lc / 2;
            rws.insert(rw);
            add(rw);
        }
        else
        {
            int p;
            cin >> p;
            tram[pass[p - 1]] = false;
            int rw = pass[p - 1] / 2;
            if (!tram[2*rw] && !tram[2*rw + 1]) rws.erase(rw);
            add(rw);
        }
    }
}

Subtask #1
10.0 / 10.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 #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 2 ms 492 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1896 KB Output is correct
2 Incorrect 32 ms 1048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3808 KB Output is correct
2 Incorrect 34 ms 1048 KB Output isn't correct
3 Halted 0 ms 0 KB -