Submission #160577

#	Time	Username	Problem	Language	Result	Execution time	Memory
160577		lyc	Tram (CEOI13_tram)	C++14	0 / 100	1087 ms	5792 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_M = 30005;

int N, M;

map<int, int> tram;
set<pair<ll,ii> > cp;
ii rec[MX_M];

bool opp(int c, ii p) {
    return (p.sc & (1<<c)) == 0;
}

ll f(int r, int c, ii p) {
    //cout << "f " << r << " " << c << " from " << p.fi << " " << p.sc << " opp " << opp(c,p) << endl;
    return (ll) (p.fi - r) * (p.fi - r) + opp(c, p);
}

ll eval(int r, int c) {
    ll res;
    if (tram.empty()) res = 0;
    else if (tram.count(r) && (tram[r] & (1<<c))) res = -1;
    else {
        auto j = tram.lower_bound(r);
        if (j == tram.begin()) res = f(r,c,*j);
        else {
            auto i = prev(j);
            res = min(f(r,c,*i), f(r,c,*j));
        }
    }
    return res;
    //return min(f(r,c,*i), f(r,c,*j));
}

void addLoc(ii p) {
    tram[p.fi] |= (1<<p.sc);
}

void delLoc(ii p) {
    tram[p.fi] &= ~(1<<p.sc);
    if (tram[p.fi] == 0) tram.erase(p.fi);
}

ld intersect(int c, ii p, ii q) {
    return ((ld) q.fi * q.fi + opp(c, q) - (ld) p.fi * p.fi - opp(c,p)) / (2.0 * (q.fi - p.fi));
}

pair<ll,ii> getCP(int c, ii p, ii q) {
    double x = intersect(c,p,q);
    int a = (int)round(floor(x)), b = (int)round(ceil(x));
    ll av = min(f(a,c,p),f(a,c,q)), bv = min(f(b,c,p),f(b,c,q));
    //cout << x << endl;
    //cout << "candidates " << a << "," << av << " and " << b << "," << bv << endl;
    if (av >= bv) return mp(-av,ii(a,c));
    else return mp(-bv,ii(b,c));
}

void addCP(int c, ii p, ii q) {
    auto pqCP = getCP(c,p,q);
    cp.insert(pqCP);
    //cout << "add " << pqCP.fi << " " << pqCP.sc.fi << " " << pqCP.sc.sc << endl;
}

void delCP(int c, ii p, ii q) {
    auto pqCP = getCP(c,p,q);
    //cout << "del " << pqCP.fi << " " << pqCP.sc.fi << " " << pqCP.sc.sc << endl;
    auto it = cp.find(pqCP);
    if (it != cp.end()) cp.erase(it);
}

void dbg() {
    cout << "==========================================" << endl;
    cout << "TRAM: ";
    for (auto x : tram) cout << "(" << x.fi << "," << x.sc << ") ";
    cout << endl;

    cout << "CP: ";
    for (auto x : cp) cout << "(" << x.fi << "," << x.sc.fi << "," << x.sc.sc << ") ";
    cout << endl;
    cout << "==========================================" << endl;
    cout << endl;
}

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

    cin >> N >> M;
    FOR(Mi,1,M){
        char T; cin >> T;
        if (T == 'E') {
            // get the maximum of points and extrema as loc
            pair<ll,ii> best = mp(-2,ii(-1,-1));
            ll tmp;
            if ((tmp = eval(N,1)) >= best.fi) best = mp(tmp,ii(N,1));
            if ((tmp = eval(N,0)) >= best.fi) best = mp(tmp,ii(N,0));
            if ((tmp = eval(1,1)) >= best.fi) best = mp(tmp,ii(1,1));
            if ((tmp = eval(1,0)) >= best.fi) best = mp(tmp,ii(1,0));
            if (!cp.empty() && (-cp.begin()->fi > best.fi || (-cp.begin()->fi == best.fi && (cp.begin()->sc.fi < best.sc.fi || (cp.begin()->sc.fi == best.sc.fi && cp.begin()->sc.sc < best.sc.sc)))))
                best = *cp.begin(), cp.erase(cp.begin());

            // record loc;
            rec[Mi] = best.sc;

            // add loc to tram
            addLoc(rec[Mi]);
            map<int,int>::iterator it = tram.lower_bound(best.sc.fi), jt;

            // remove old point btw prev and next
            if (it != tram.begin() && next(it) != tram.end()) {
                delCP(0,*prev(it),*next(it));
                delCP(1,*prev(it),*next(it));
            }
            // add new point with prev, if any
            if (it != tram.begin()) {
                addCP(0,*prev(it),*it);
                addCP(1,*prev(it),*it);
            }
            // add new point with next
            if (next(it) != tram.end()) {
                addCP(0,*it,*next(it));
                addCP(1,*it,*next(it));
            }
            
            // print ans
            cout << rec[Mi].fi << " " << rec[Mi].sc+1 << endl;
        } else {
            int P; cin >> P;
            // retrieve loc
            ii loc = rec[P];
            map<int,int>::iterator it = tram.lower_bound(loc.fi), jt;

            // remove old point with prev
            if (it != tram.begin()) {
                delCP(0,*prev(it),*it);
                delCP(1,*prev(it),*it);
            }
            // remove old point with next
            if (next(it) != tram.end()) {
                delCP(0,*it,*next(it));
                delCP(1,*it,*next(it));
            }
            // add new point btw prev and next
            if (it != tram.begin() && next(it) != tram.end()) {
                addCP(0,*prev(it),*next(it));
                addCP(1,*prev(it),*next(it));
            }

            // remove loc from tram
            delLoc(loc);
        }
        //dbg();
    }
}

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