Submission #69443186

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>
#include <inttypes.h>
void* malloc_check(size_t size) {
  void* res = malloc(size);
  if (res == NULL) exit(2);
  return res;
}
int Q;
int query[512345][3];
/* 1. 一旦削除クエリを無視し、挿入クエリのみを処理して順番の情報を得る */
struct node_s {
  int value;
  struct node_s* next;
};
struct node_s* num_to_node[512345];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

void* malloc_check(size_t size) {
	void* res = malloc(size);
	if (res == NULL) exit(2);
	return res;
}

int Q;
int query[512345][3];

/* 1. 一旦削除クエリを無視し、挿入クエリのみを処理して順番の情報を得る */

struct node_s {
	int value;
	struct node_s* next;
};

struct node_s* num_to_node[512345];
int num_to_pos[512345];

/* 2. 区間更新・区間和のセグメント木でクエリを処理する */

#define KI_MAX (1 << 19) /* 524288 */

int64_t ki[KI_MAX * 2 - 1], ki_all[KI_MAX * 2 - 1];
char ki_all_valid[KI_MAX * 2 - 1];

int64_t ki_set_i(int idx, int ss, int se, int qs, int qe, int64_t value) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all[idx] = value;
		ki_all_valid[idx] = 1;
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		int64_t l, r;
		if (ki_all_valid[idx]) {
			ki_all[idx * 2 + 1] = ki_all[idx];
			ki_all[idx * 2 + 2] = ki_all[idx];
			ki_all_valid[idx * 2 + 1] = 1;
			ki_all_valid[idx * 2 + 2] = 1;
			ki_all_valid[idx] = 0;
		}
		l = ki_set_i(idx * 2 + 1, ss, sm, qs, qe, value);
		r = ki_set_i(idx * 2 + 2, sm, se, qs, qe, value);
		ki[idx] = l + r;
	}
	return ki_all_valid[idx] ? ki_all[idx] * (se - ss) : ki[idx];
}

void ki_set(int qs, int qe, int64_t value) {
	ki_set_i(0, 0, KI_MAX, qs, qe, value);
}

int64_t ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki_all_valid[idx] ? ki_all[idx] * (se - ss) : ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return 0;
	} else if (ki_all_valid[idx]) { /* 全体セット済、一部のみ反映 */
		int s = ss < qs ? qs : ss;
		int e = se < qe ? se : qe;
		return ki_all[idx] * (e - s);
	} else {
		int sm = ss + (se - ss) / 2;
		int64_t l, r;
		l = ki_get_i(idx * 2 + 1, ss, sm, qs, qe);
		r = ki_get_i(idx * 2 + 2, sm, se, qs, qe);
		return l + r;
	}
}

int64_t ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int main(void) {
	int i;
	struct node_s* np;
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 1; i <= Q; i++) {
		if (scanf("%d%d", &query[i][0], &query[i][1]) != 2) return 1;
		if (query[i][0] == 2 && scanf("%d", &query[i][2]) != 1) return 1;
	}

	/* 1 */
	num_to_node[0] = malloc_check(sizeof(struct node_s));
	num_to_node[0]->value = 0;
	num_to_node[0]->next = NULL;
	for (i = 1; i <= Q; i++) {
		if (query[i][0] == 1) {
			struct node_s* new_node = malloc_check(sizeof(struct node_s));
			new_node->value = i;
			new_node->next = num_to_node[query[i][1]]->next;
			num_to_node[query[i][1]]->next = new_node;
			num_to_node[i] = new_node;
		}
	}
	for (i = 0, np = num_to_node[0]; np != NULL; i++, np = np->next) {
		num_to_pos[np->value] = i;
	}

	/* 2 */
	for (i = 1; i <= Q; i++) {
		if (query[i][0] == 1) {
			int pos = num_to_pos[i];
			ki_set(pos, pos + 1, i);
		} else if (query[i][0] == 2) {
			int pos1 = num_to_pos[query[i][1]];
			int pos2 = num_to_pos[query[i][2]];
			if (pos1 > pos2) {
				int t = pos1;
				pos1 = pos2;
				pos2 = t;
			}
			printf("%" PRId64 "\n", ki_get(pos1 + 1, pos2));
			ki_set(pos1 + 1, pos2, 0);
		}
	}

	return 0;
}

Submission Info

Judge Result