Submission #780909

#	Time	Username	Problem	Language	Result	Execution time	Memory
780909		79brue	Tram (CEOI13_tram)	C++17	100 / 100	31 ms	6452 KiB

tram

#include <bits/stdc++.h>
#define PAIR(x,y) ((x)*2+(y))

using namespace std;

typedef long long ll;

int n, q;

struct Info{
    int l, r, ss, es; /// ss: l-1 상태, es: r+1 상태
    int PR;

    Info(){}
    Info(int l, int r, int ss, int es): l(l), r(r), ss(ss), es(es){
        if(l==1 && r==n) PR = 1e9;
        else if(l==1 || r==n) PR = (ss|es)==3 ? PAIR(r-l+1, 0) : PAIR(r-l+1, 1);
        else if(ss==3 && es==3) PR = PAIR((r-l)/2+1, 0);
        else if((ss|es)==3) PR = PAIR((r-l)/2+1, (r-l)%2);
        else PR = PAIR((r-l)/2+1, 1);
    }

    bool operator<(const Info &nxt)const{
        if(PR != nxt.PR) return PR > nxt.PR;
        return l<nxt.l;
    }
};

int arr[150002][2];
int qx[30002], qy[30002];

set<Info> st; /// 행과 행 사이의 틈 관리
set<pair<int, int> > interval; /// st에서 (l, r)만 관리
set<pair<int, int> > blank; /// 한 열만 사람이 탄 행을 관리

int calc(int x){
    return arr[x][0]+arr[x][1]*2;
}

int findLoc(Info p){
    int l = p.l, r = p.r, ss=p.ss, es=p.es;
    if(l==1 && r==n) return PAIR(1, 0);
    else if(l==1 || r==n) return PAIR(l==1 ? 1 : n, (ss|es)==1 ? 1 : 0);
    else if(es==3) return PAIR((l+r)/2, (ss==1 && (r-l)%2) ? 1 : 0);
    else if(ss==3) return PAIR((l+r+1)/2, (es==1 && (r-l)%2) ? 1 : 0);
    else if(ss==es) return PAIR((l+r)/2, ss==1 ? 1 : 0);
    else            return PAIR((l+r)/2, (ss==1 && (r-l)%2) ? 1 : 0);
}

void checkAndResume(int x, int a, int b, bool c){
    auto it = interval.lower_bound(make_pair(x, INT_MAX));
    if(it == interval.begin() || prev(it)->second < x) return;
    --it;
    int l = it->first, r = it->second;
    Info p = Info(l, r, calc(l-1), calc(r+1));
    st.erase(p);
    arr[a][b] = c;
    p = Info(l, r, calc(l-1), calc(r+1));
    st.insert(p);
    arr[a][b] = !c;
}

void put(int idx){
    ll PR1 = st.empty() ? -1 : st.begin()->PR;
    int p1 = st.empty() ? INT_MAX : findLoc(*st.begin());
    ll PR2 = blank.empty() ? -1 : 2;
    int p2 = blank.empty() ? INT_MAX : PAIR(blank.begin()->first, blank.begin()->second);

    int loc = (PR1 > PR2) ? p1 : (PR1 < PR2) ? p2 : min(p1, p2);
    int x = loc/2, y = loc%2;
    qx[idx] = x, qy[idx] = y;

    printf("%d %d\n", x, y+1);

    /// blank 갱신
    if(arr[x][!y] == 1){
        blank.erase(make_pair(x, y));
        checkAndResume(x-1, x, y, 1);
        checkAndResume(x+1, x, y, 1);
        arr[x][y] = 1;
        return;
    }
    else{
        blank.insert(make_pair(x, !y));
    }
    arr[x][y] = 1;

    /// st 갱신
    Info tmp = *st.begin(); st.erase(st.begin()); interval.erase(make_pair(tmp.l, tmp.r));
    if(tmp.l != x){
        st.insert(Info(tmp.l, x-1, calc(tmp.l-1), calc(x)));
        interval.insert(make_pair(tmp.l, x-1));
    }
    if(tmp.r != x){
        st.insert(Info(x+1, tmp.r, calc(x), calc(tmp.r+1)));
        interval.insert(make_pair(x+1, tmp.r));
    }
}

void erase(int x, int y){
    if(arr[x][!y]){
        blank.insert(make_pair(x, y));
        checkAndResume(x-1, x, y, 0);
        checkAndResume(x+1, x, y, 0);
        arr[x][y] = 0;
        return;
    }
    else{
        blank.erase(make_pair(x, !y));
    }

    int l = x, r = x;
    auto it = interval.lower_bound(make_pair(x, 0));
    if(it != interval.begin() && prev(it)->second == x-1){
        l = prev(it)->first;
        st.erase(Info(prev(it)->first, prev(it)->second, calc(prev(it)->first-1), calc(prev(it)->second+1)));
        interval.erase(prev(it));
    }
    if(it != interval.end() && it->first == x+1){
        r = it->second;
        st.erase(Info(it->first, it->second, calc(it->first-1), calc(it->second+1)));
        interval.erase(it);
    }

    arr[x][y] = 0;

    interval.insert(make_pair(l, r));
    st.insert(Info(l, r, calc(l-1), calc(r+1)));
}

int main(){
    scanf("%d %d", &n, &q);
    st.insert(Info(1, n, 0, 0));
    for(int i=1; i<=q; i++){
        char c;
        int x;
        scanf(" %c", &c);
        if(c=='E') put(i), x=i;
        else{
            scanf("%d", &x);
            erase(qx[x], qy[x]);
        }

//        printf("After query %d (%d, %d)\n", i, qx[x], qy[x]+1);
//        for(auto p: interval) printf("[%d, %d] ", p.first, p.second); puts("");
//        for(Info p: st) printf("[%d, %d] (%d %d), ", p.l, p.r, p.ss, p.es); puts("");
    }
}

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:140:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

• 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