Submission #160639

#	Time	Username	Problem	Language	Result	Execution time	Memory
160639		lyc	Tram (CEOI13_tram)	C++14	100 / 100	102 ms	4588 KiB

tram

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 150005;
const int MX_M = 30005;

struct P {
    int a, b; ll v;
    bool operator<(const P& p) const {
        if (v == p.v) {
            if (a == p.a) return b < p.b;
            return a < p.a;
        }
        return v > p.v;
    }
};

int N, M;
int A[MX_N];
ii rec[MX_M];
set<P> val;
set<int> occ;

P calc(int l, int r) {
    l = max(l,1); r = min(r,N);
    int m = (l+r)/2;

    P best = {-1,-1,-1};
    vector<ii> pts;
    if (!(A[l]&2)) pts.emplace_back(l,1);
    if (!(A[l]&4)) pts.emplace_back(l,2);
    if (l < r) {
        if (!(A[m]&2)) pts.emplace_back(m,1);
        if (!(A[m]&4)) pts.emplace_back(m,2);
        if (!(A[m+1]&2)) pts.emplace_back(m+1,1);
        if (!(A[m+1]&4)) pts.emplace_back(m+1,2);
        if (!(A[r]&2)) pts.emplace_back(r,1);
        if (!(A[r]&4)) pts.emplace_back(r,2);
    }
    for (auto x : pts) {
        auto it = occ.lower_bound(x.fi);
        ll cost = 1e18;
        if (x.fi == *it) {
            cost = 1;
        } else {
            auto prv = *prev(it), nxt = *it;
            if (prv != 0) cost = min(cost, (ll) (prv-x.fi) * (prv-x.fi) + ((A[prv]&(1<<x.sc)) == 0));
            if (nxt != N+1) cost = min(cost, (ll) (nxt-x.fi) * (nxt-x.fi) + ((A[nxt]&(1<<x.sc)) == 0));
        }
        P cur = {x.fi,x.sc,cost};
        if (cur < best) best = cur;
    }
    //cout << "BEST: " << best.a << " " << best.b << " :: " << best.v << endl;
    return best;
}

void dbg() {
    cout << "==========================================" << endl;
    cout << "TRAM: ";
    for (auto x : occ) cout << x << ':' << A[x] << ' '; 
    cout << endl;

    cout << "VAL: ";
    for (auto x : val) cout << '[' << x.a << ',' << x.b << "]:" << x.v << ' ';
    cout << endl;
    cout << "==========================================" << endl;
    cout << endl;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    occ.insert(0); occ.insert(N+1);
    val.insert(calc(0,N+1));
    A[0] = A[N+1] = 6;
    FOR(i,1,M){
        char T; cin >> T;
        if (T == 'E') {
            auto cur = *val.begin();
            auto it = occ.lower_bound(cur.a);
            if (cur.a == *it) {
                if (it != occ.begin()) val.erase(calc(*prev(it),cur.a));
                if (next(it) != occ.end()) val.erase(calc(cur.a,*next(it)));
                A[cur.a] |= (1<<cur.b);
                if (it != occ.begin()) val.insert(calc(*prev(it),cur.a));
                if (next(it) != occ.end()) val.insert(calc(cur.a,*next(it)));
            } else {
                auto prv = *prev(it), nxt = *it;
                val.erase(calc(prv,nxt));
                occ.insert(cur.a);
                A[cur.a] |= (1<<cur.b);
                val.insert(calc(prv,cur.a));
                val.insert(calc(cur.a,nxt));
            }
            cout << cur.a << ' ' << cur.b << '\n';
            rec[i] = ii(cur.a, cur.b);
        } else {
            int P; cin >> P;
            auto cur = rec[P];
            auto it = occ.find(cur.fi);
            auto prv = *prev(it), nxt = *next(it);
            val.erase(calc(prv,cur.fi));
            val.erase(calc(cur.fi,nxt));
            A[cur.fi] &= ~(1<<cur.sc);
            if (A[cur.fi] == 0) {
                occ.erase(it);
                val.insert(calc(prv,nxt));
            } else {
                val.insert(calc(prv,cur.fi));
                val.insert(calc(cur.fi,nxt));
            }
        }
        //dbg();
    }
}

• 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