제출 #256885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256885		doowey	전차 (CEOI13_tram)	C++14	100 / 100	316 ms	19052 KiB

tram

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
const ll inf = (ll)1e14;
set<pii> pos;
set<int> rows;
set<pair<ll,pii>> shit;
bool has[N][2];

int n;

vector<pii> cells(int l, int r){
    vector<pii> res;
    for(int i = 0 ; i < 2; i ++ ){
        if(!has[l][i]){
            res.push_back(mp(l, i));
        }
        if(!has[l+1][i]){
            res.push_back(mp(l+1,i));
        }
    }
    for(int i = 0 ; i < 2; i ++ ){
        if(r > l + 1){
            if(!has[r][i]){
                res.push_back(mp(r, i));
            }
            if(r - 1 > l + 1){
                if(!has[r - 1][i]){
                    res.push_back(mp(r-1,i));
                }
            }
        }
    }
    if((r - l - 1) >= 3){
        int mid = (l + r) / 2;
        for(int q = 0; q < 2; q ++ ){
            res.push_back(mp(mid,q));
            if((r - l - 1) % 2 == 0)
                res.push_back(mp(mid + 1, q));
        }
    }
    return res;
}

ll Q(ll d){
    return d * d;
}

ll compute(int x, int y){
    ll ans = inf;
    auto it = pos.lower_bound(mp(x,y));
    auto pv = it;
    for(int q = 0; q < 2; q ++ ){
        if(it != pos.end()){
            ans = min(ans, Q(it->fi - x) + Q(it->se - y));
            it ++ ;
        }
    }
    for(int q = 0; q < 2 ; q ++ ){
        if(pv != pos.begin()) pv -- ;
        if(pv != pos.end()){
            ans = min(ans, Q(pv->fi - x) + Q(pv->se - y));
        }
    }
    return ans;
}

void add(int x, int y){
    auto it = rows.upper_bound(x);
    auto pv = it;
    pv -- ;
    vector<pii> shi = cells(*pv, *it);
    for(auto f : shi)
        shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    auto qq = pv;
    if(qq != rows.begin()){
        qq -- ;
        if(*pv == x){
            shi = cells(*qq, *pv);
            for(auto f : shi)
                shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
        }
    }
    has[x][y]=true;
    pos.insert(mp(x,y));
    rows.insert(x);
    it = rows.lower_bound(x);
    pv = it;
    pv -- ;
    shi = cells(*pv, *it);
    for(auto f : shi)
        shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    pv = it;
    pv ++ ;
    shi = cells(*it, *pv);
    for(auto f : shi)
        shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
}

void delet(int x, int y){
    auto it = rows.lower_bound(x);
    auto pv = it;
    pv --;
    vector<pii> shi = cells(*pv, *it);
    for(auto f : shi)
        shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    pv = it;
    pv ++ ;
    shi = cells(*it, *pv);
    for(auto f : shi)
        shit.erase(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    pos.erase(mp(x,y));
    has[x][y]=false;
    if(!has[x][0] && !has[x][1]){
        rows.erase(x);
        it = rows.lower_bound(x);
        pv = it;
        pv -- ;
        shi = cells(*pv, *it);
        for(auto f : shi)
            shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    }
    else{
        it = rows.lower_bound(x);
        pv = it;
        pv -- ;
        shi = cells(*pv, *it);
        for(auto f : shi)
            shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
        pv = it;
        pv ++ ;
        shi = cells(*it, *pv);
        for(auto f : shi)
            shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    }
}

pii id[N];

int main(){
    fastIO;
    int q;
    cin >> n >> q;
    rows.insert(0);
    rows.insert(n+1);
    for(int q = 0; q < 2; q ++ ){
        has[0][q]=true;
        has[n+1][q]=true;
    }
    vector<pii> shi = cells(0, n + 1);
    for(auto f : shi)
        shit.insert(mp(compute(f.fi, f.se), mp(f.fi, f.se)));
    char typ;
    pii cur;
    int tyi;
    ll dis;
    for(int t = 0; t < q; t ++ ){
        cin >> typ;
        if(typ == 'E'){
            auto fx = shit.end();
            -- fx;
            if(fx->fi == inf){
                id[t] = mp(1,0);
                add(1,0);
                cout << 1 << " " << 1 << "\n";
            }
            else{
                dis = fx->fi;
                fx = shit.lower_bound(mp(dis,mp(-1,-1)));
                id[t] = mp(fx->se.fi, fx->se.se);
                cout << fx->se.fi << " " << fx->se.se + 1 << "\n";
                add(fx->se.fi, fx->se.se);
            }
        }
        else{
            cin >> tyi;
            tyi--;
            delet(id[tyi].fi, id[tyi].se);
        }
    }
    return 0;
}

• 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