#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
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);
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
312 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
2004 KB |
Output is correct |
| 2 |
Correct |
13 ms |
724 KB |
Output is correct |
| 3 |
Correct |
21 ms |
1876 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
6452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
732 KB |
Output is correct |
| 3 |
Correct |
30 ms |
3248 KB |
Output is correct |
