백준 34738 (C++) Game of Pieces

최초 업로드: 2025-11-15 03:36:42

최근 수정 시간: 2025-11-15 03:36:42

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] Game of Pieces

[문제 링크](https://www.acmicpc.net/problem/34738)

## 문제 설명

If you’ve ever played Tetris for long enough, you might have experienced the Tetris effect – seeing falling blocks even after you have stopped playing. To stay focused on solving problems and avoid such distractions, we will consider a simplified version of the game.

The game is played on a board composed of square cells arranged in a grid. Columns of the grid are numbered sequentially from left to right. The board is infinite to the right and to the top. Each cell is either empty or filled, and initially, all cells are empty.

A sequence of N rectangular pieces is given, and the pieces are dropped onto the board one at a time. Pieces have different sizes. A piece of size $L$ is either vertical ($L \times 1$ cells) or horizontal ($1 \times L$ cells). When a piece is dropped at a specified column, it starts at a location above all the currently filled cells and falls straight down until it either reaches the bottom of the board or lands on top of an already filled cell. Once a piece lands, it fills its final set of cells.

Each time a piece lands, the game is considered safe if no empty cell has a filled cell above it; otherwise the game is unsafe, the offending piece is removed from the board, and the game continues with the next piece as if it had never been dropped.

In the example below, corresponding to the first sample input, the game becomes unsafe once the second piece lands, hence the piece is removed and the next pieces keep the game safe.

Given the sequence of pieces and their drop positions, your task is to determine, for each piece, whether it makes the board unsafe after landing.

## 입력

The first line contains an integer $N$ ($1 ≤ N ≤ 2 \cdot 10^5$), indicating the number of pieces.

Each of the next $N$ lines describes a piece with a character $C$ and two integers $L$ and $P$ ($1 ≤ L ≤ 10^9$ and $1 ≤ P ≤ 10^{18}$), representing respectively the type of the piece, its length, and the position where it is dropped. For a vertical piece, $C$ is the character “<code>|</code>” (pipe), the piece has $L \times 1$ cells, and it is dropped at column $P$. For a horizontal piece, $C$ is the character “<code>-</code>” (hyphen), the piece has $1 \times L$ cells, and it is dropped spanning columns $P, P + 1, \dots , P + L − 1$.

## 출력

Output a single line with a string of length $N$. The $i$-th character of the string must be the uppercase letter “<code>U</code>” if the game becomes unsafe immediately after the $i$-th piece lands on the board, and the uppercase letter “<code>S</code>” otherwise.

## 풀이
들어오는 블럭의 왼쪽 끝, 오른쪽 끝, 오른쪽 끝+1 만 기억해서 좌표압축을 한 후, 구간 쿼리를 날려 최댓값과 최솟값이 같은지를 통해 평평한지 여부를 확인할 수 있습니다.

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

typedef long long ll;
const int MAX = 600'001*4;

ll _size=1, segMin[MAX], segMax[MAX], lazyMin[MAX], lazyMax[MAX];

void updateLazy(int nodeNum, int nodeL, int nodeR) {
    if(lazyMin[nodeNum]) {
        segMin[nodeNum] += lazyMin[nodeNum];
        segMax[nodeNum] += lazyMax[nodeNum];
        if(nodeL!=nodeR) {
            lazyMin[nodeNum*2] += lazyMin[nodeNum];
            lazyMin[nodeNum*2+1] += lazyMin[nodeNum];
            lazyMax[nodeNum*2] += lazyMax[nodeNum];
            lazyMax[nodeNum*2+1] += lazyMax[nodeNum];
        }
        lazyMin[nodeNum]=lazyMax[nodeNum]=0;
    }
}

void updateRange(int L, int R, ll val, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 updateLazy(nodeNum, nodeL, nodeR);
 if(R<nodeL || nodeR<L) return;
 if(L<=nodeL && nodeR<=R) {
 lazyMin[nodeNum] = lazyMax[nodeNum] = val;
 updateLazy(nodeNum, nodeL, nodeR);
 } else {
 int mid = nodeL+nodeR>>1;
 updateRange(L, R, val, nodeNum*2, nodeL, mid);
 updateRange(L, R, val, nodeNum*2+1, mid+1, nodeR);
 segMin[nodeNum] = min(segMin[nodeNum*2], segMin[nodeNum*2+1]);
 segMax[nodeNum] = max(segMax[nodeNum*2], segMax[nodeNum*2+1]);
 }
}

ll searchMin(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 updateLazy(nodeNum, nodeL, nodeR);
 if(R<nodeL || nodeR<L) return LONG_LONG_MAX;
 if(L<=nodeL && nodeR<=R) return segMin[nodeNum];
 int mid = nodeL+nodeR>>1;
 return min(searchMin(L, R, nodeNum*2, nodeL, mid), searchMin(L, R, nodeNum*2+1, mid+1, nodeR));
}

ll searchMax(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 updateLazy(nodeNum, nodeL, nodeR);
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return segMax[nodeNum];
 int mid = nodeL+nodeR>>1;
 return max(searchMax(L, R, nodeNum*2, nodeL, mid), searchMax(L, R, nodeNum*2+1, mid+1, nodeR));
}

struct element {
    char ch; ll l, p;
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector<element> v(n);
 vector<ll> vals;
 for(int i=0;i<n;i++) {
 cin >> v[i].ch >> v[i].l >> v[i].p;
 vals.push_back(v[i].p);
 if(v[i].ch=='-') {
 vals.push_back(v[i].p+v[i].l-1);
 vals.push_back(v[i].p+v[i].l);
 }
 else vals.push_back(v[i].p+1);
 }
 sort(vals.begin(), vals.end());
 vals.erase(unique(vals.begin(), vals.end()), vals.end());

while(_size<vals.size()) _size<<=1;
 _size<<=1;

for(auto [ch, l, p] : v) {
 int lo = lower_bound(vals.begin(), vals.end(), p)-vals.begin();
 if(ch=='|') {
 cout << 'S';
 updateRange(lo, lo, l);
 } else {
 int hi = lower_bound(vals.begin(), vals.end(), p+l-1)-vals.begin();
 if(searchMin(lo, hi)!=searchMax(lo, hi)) {
 cout << 'U';
 } else {
 cout << 'S';
 updateRange(lo, hi, 1);
 }
 }
 }
}
```