글 읽기 - O(KHW + NM log N + QH log H)로 풀었는데 TLE

h0ngjun7 6년 전 0

계산해보면 시간 안에 나와야할 것 같은데, 참으로 안타까울 따름입니다.

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

int N, M, K;
char S[1002][1002], t[502];
int H[502], W[502];
char A[502][502][502];
set <int> s[1002];

struct QUERY {
	int k, x, y;
} q[10002];

int main(void) {
	scanf("%d%d%d\n",&N,&M,&K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			s[i].insert(j);
			S[i][j] = '.';
		}
	}
	for (int k = 0; k < K; k++) {
		scanf("%d%d\n",&H[k],&W[k]);
		for (int i = 0; i < H[k]; i++) fgets(A[k][i], 502, stdin);
	}
	int Q; scanf("%d",&Q);
	for (int i = 1; i <= Q; i++) {
		scanf("%d%d%d",&q[i].k,&q[i].x,&q[i].y);
	}
	for (int i = Q; i >= 1; i--) {
		int k = q[i].k - 1, XL = q[i].x + H[k], YL = q[i].y + W[k];
		for (int x = q[i].x; x < XL; x++) {
			for (auto it = s[x].lower_bound(q[i].y); it != s[x].end() && (*it) < YL; ) {
				S[x][*it] = A[k][x-q[i].x][(*it)-q[i].y];
				it = s[x].erase(it);
			}
		}
	}
	for (int i = 0; i < N; i++) puts(S[i]);
    return 0;
}

h0ngjun7 6년 전 0

어멋.. 아주 작은 편법(?!)을 써서 996ms에 맞추어버렸네요.

yukariko 6년 전 0

ㅠㅠ 죄송합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

O(KHW + NM log N + QH log H)로 풀었는데 TLE

h0ngjun7 6년 전 0

h0ngjun7 6년 전 0

yukariko 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말