Submission #69289617

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct elem_s {
  long long tr; /* tai ryoku */
  int id;
};
int cmp_elem(const struct elem_s* a, const struct elem_s* b) {
  if (a->tr != b->tr) return a->tr < b->tr ? -1 : 1;
  return a->id < b->id ? -1 : a->id > b->id;
}
struct pq_s {
  int size, capacity;
  struct elem_s* elems;
};
void pq_adjust(struct pq_s* pq, int node) {
  for (;;) {
    int minidx = node;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct elem_s {
	long long tr; /* tai ryoku */
	int id;
};

int cmp_elem(const struct elem_s* a, const struct elem_s* b) {
	if (a->tr != b->tr) return a->tr < b->tr ? -1 : 1;
	return a->id < b->id ? -1 : a->id > b->id;
}

struct pq_s {
	int size, capacity;
	struct elem_s* elems;
};

void pq_adjust(struct pq_s* pq, int node) {
	for (;;) {
		int minidx = node;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = node * 2 + i;
			if (c < pq->size && cmp_elem(&pq->elems[minidx], &pq->elems[c]) > 0) minidx = c;
		}
		if (minidx == node) {
			if (node == 0) return;
			node = (node - 1) / 2;
		} else {
			struct elem_s tmp = pq->elems[node];
			pq->elems[node] = pq->elems[minidx];
			pq->elems[minidx] = tmp;
			node = minidx;
		}
	}
}

void pq_add(struct pq_s* pq, struct elem_s elem) {
	if (pq->size >= pq->capacity) {
		pq->elems = realloc(pq->elems, sizeof(*pq->elems) * (pq->capacity = pq->size + 1));
		if (pq->elems == NULL) exit(2);
	}
	pq->elems[pq->size++] = elem;
	pq_adjust(pq, pq->size - 1);
}

struct elem_s pq_get(struct pq_s* pq) {
	struct elem_s res;
	if (pq->size <= 0) exit(42);
	res = pq->elems[0];
	if (--pq->size > 0) {
		pq->elems[0] = pq->elems[pq->size];
		pq_adjust(pq, 0);
	}
	return res;
}

struct pqd_s {
	struct pq_s data, deleted;
};

void pqd_sousai(struct pqd_s* pqd) {
	while (
		pqd->data.size > 0 &&
		pqd->deleted.size > 0 &&
		pqd->data.elems[0].tr == pqd->deleted.elems[0].tr &&
		pqd->data.elems[0].id == pqd->deleted.elems[0].id
	) {
		pq_get(&pqd->data);
		pq_get(&pqd->deleted);
	}
}

void pqd_add(struct pqd_s* pqd, struct elem_s elem) {
	pq_add(&pqd->data, elem);
}

void pqd_delete(struct pqd_s* pqd, struct elem_s elem) {
	pq_add(&pqd->deleted, elem);
}

int pqd_size(struct pqd_s* pqd) {
	return pqd->data.size - pqd->deleted.size;
}

struct elem_s pqd_peek(struct pqd_s* pqd) {
	pqd_sousai(pqd);
	if (pqd->data.size <= 0) exit(42);
	return pqd->data.elems[0];
}

struct elem_s pqd_get(struct pqd_s* pqd) {
	pqd_sousai(pqd);
	return pq_get(&pqd->data);
}

int N, Q;
int A[212345];
int event[212345], x[212345], y[212345];

struct pqd_s tr_pqd;
struct elem_s trs[212345];

int ans_cnt;
int ans[212345];

int cmp_int(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

void sort_and_print_ans(void) {
	int i;
	qsort(ans, ans_cnt, sizeof(*ans), cmp_int);
	printf("%d", ans_cnt);
	for (i = 0; i < ans_cnt; i++) {
		printf(" %d", ans[i]);
	}
	putchar('\n');
}

int main(void) {
	int i;
	long long offset = 0;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d%d", &event[i], &x[i], &y[i]) != 3) return 1;
	}

	for (i = 1; i <= N; i++) {
		trs[i].tr = A[i];
		trs[i].id = i;
		pqd_add(&tr_pqd, trs[i]);
	}

	for (i = 0; i < Q; i++) {
		ans_cnt = 0;
		if (event[i] == 1) {
			pqd_delete(&tr_pqd, trs[x[i]]);
			trs[x[i]].tr += y[i];
			offset -= y[i];
			pqd_add(&tr_pqd, trs[x[i]]);
			while (pqd_size(&tr_pqd) > 0 && pqd_peek(&tr_pqd).tr + offset <= 0) {
				ans[ans_cnt++] = pqd_get(&tr_pqd).id;
			}
		} else if (event[i] == 2) {
			pqd_delete(&tr_pqd, trs[x[i]]);
			trs[x[i]].tr -= y[i];
			if (trs[x[i]].tr + offset > 0) {
				pqd_add(&tr_pqd, trs[x[i]]);
			} else {
				ans[ans_cnt++] = x[i];
			}
		}
		sort_and_print_ans();
	}

	return 0;
}

Submission Info

Judge Result