oj.uz

Submission #270614

# Submission time Handle Problem Language Result Execution time Memory
270614 2020-08-17T19:57:39 Z johutha Tram (CEOI13_tram) C++17
80 / 100
 71 ms 5980 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 (rw >= n) return;
        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);
        addrw(nx);
        addrw(pr);
        addrw(pr + 1);
        addrw(nx + 1);
    };
 
    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 3 ms 620 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 5 ms 620 KB Output is correct

Subtask #4
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 620 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2220 KB Output is correct
2 Correct 51 ms 1308 KB Output is correct
3 Correct 69 ms 3172 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5980 KB Output is correct
2 Incorrect 48 ms 1308 KB Output isn't correct
3 Halted 0 ms 0 KB -