총으로 하나의 층을 없앨 수 있는데 맥주캔의 종류(검,회,흰)에따라 점수를 획득한다.
M개의 쿼리를 입력받아 해당 층을 없앨 때 점수를 구하는 문제다.
N과 M이 300,000이나 되고 하나의 열에 최대 3,000,000층 만큼의 맥주가 쌓일 수 있다.
쿼리를 받을때마다 일일이 처리하는건 절대 안되고 굉장히 크기가 큰만큼 메모리도 신경써야한다.
처음에는 segment tree와 lazy propagation로 3,000,000층에서 각층의 점수를 누적해서 저장해주었다.
근데 long long 변수로 저장하고 이러한 segment tree를 2개 저장했으니 8*16*3,000,000 byte가 필요하였다.
그래서 메모리초과가 발생하였다.
좀 생각해보니 각층의 점수 누적을 segment tree로 할 필요없이 일반배열에 저장해서 누적합하면 될것같았다.
그리고 각 층의 쿼리계산은 아까 구현해놓은 segment tree로 갖다 썼다.
사실 메모리초과 발생해서 틀리고 나서 못풀거같은 느낌이 들었는데 차분히 생각하니 답이 나왔다.
또 배열을 int형으로 1200만 선언을 해본적은 처음이고 되는사실도 오늘 알았다.
풀려서 기분이 좋다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int Plus[3] = { 1,2,5 };
int p[300001];
int sum[3000000];
bool chk[3000000];
struct Segment {
vector<int> tree;
int size;
Segment() {}
Segment(int N) :size(N) { tree.resize(4 * N, 0); }
int init(int node, int nl, int nr) {
if (nl == nr) return tree[node] = 1;
int mid = (nl + nr) >> 1;
return tree[node] = init(node * 2, nl, mid) + init(node * 2 + 1, mid + 1, nr);
}
void init() {
init(1, 0, size - 1);
}
int update(int idx, int val, int node, int nl, int nr) {
if (nl > idx || nr < idx) return tree[node];
if (nl == nr) return tree[node] += val;
int mid = (nl + nr) >> 1;
return tree[node] = update(idx, val, node * 2, nl, mid) + update(idx, val, node * 2 + 1, mid + 1, nr);
}
void update(int idx, int val) {
update(idx, val, 1, 0, size - 1);
}
int find(int val, int node, int nl, int nr) {
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
if (tree[node * 2] >= val) return find(val, node * 2, nl, mid);
else return find(val - tree[node * 2], node * 2 + 1, mid + 1, nr);
}
int find(int val) {
return find(val, 1, 0, size - 1);
}
};
int main() {
scanf("%d", &N);
Segment seg(3000000);
seg.init();
for (int n = 0;n < 3;n++) {
for (int m = 0, in;m < N;m++) {
scanf("%d", &in);
sum[p[m]] += Plus[n];
sum[p[m] + in] -= Plus[n];
p[m] += in;
}
}
for (int n = 0;n < 3000000;n++) {
if (n != 0) sum[n] += sum[n - 1];
}
scanf("%d", &M);
for (int m = 0, in;m < M;m++) {
scanf("%d", &in);
int idx = min(3000000 - 1, seg.find(in));
if (!chk[idx]) {
chk[idx] = true;
printf("%d\n", sum[idx]);
seg.update(idx, -1);
}
else printf("0\n");
}
return 0;
}
| cs |
전 처음 구축할 때 그냥 여사건의 법칙을 이용해서 접근했던 기억이 나네요.
답글삭제ps를 하다 보니 의외로 저런 걸 이용하느 문제가 적잖게 나오는 거 같아요..