Submission #65770889

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 <string.h>
#include <inttypes.h>
#define KI_MAX (1 << 18) /* 262144 */
int ki_all_set[KI_MAX * 2 - 1];
int ki_all_add[KI_MAX * 2 - 1];
int64_t ki[KI_MAX * 2 - 1];
int64_t ki_set_i(int idx, int ss, int se, int qs, int qe, int value) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    ki_all_set[idx] = value;
    ki_all_add[idx] = 0;
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    /* 何もしない */
  } else {
    int sm = ss + (se - ss) / 2;
    int64_t l, r;
    if (ki_all_set[idx] >= 0) {
      ki_all_set[idx * 2 + 1] = ki_all_set[idx];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define KI_MAX (1 << 18) /* 262144 */

int ki_all_set[KI_MAX * 2 - 1];
int ki_all_add[KI_MAX * 2 - 1];
int64_t ki[KI_MAX * 2 - 1];

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

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

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

void ki_add(int qs, int qe, int value) {
	ki_add_i(0, 0, KI_MAX, qs, qe, value);
}

int64_t ki_sum_i(int idx, int ss, int se, int qs, int qe) {
	int ts = ss < qs ? qs : ss;
	int te = se < qe ? se : qe;
	int64_t res = 0;
	if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 全体分の加算も行わず 0 を返す */
		return 0;
	} else if (ki_all_set[idx] >= 0) { /* 全体が一括設定されている */
		res = (int64_t)ki_all_set[idx] * (te - ts);
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		res = ki[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		int64_t l, r;
		l = ki_sum_i(idx * 2 + 1, ss, sm, qs, qe);
		r = ki_sum_i(idx * 2 + 2, sm, se, qs, qe);
		res = l + r;
	}
	return res + (int64_t)ki_all_add[idx] * (te - ts);
}

int64_t ki_sum(int qs, int qe) {
	return ki_sum_i(0, 0, KI_MAX, qs, qe);
}

int N, M;
int T[212345], L[212345], R[212345];

int main(void) {
	int i;
	int64_t ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 1; i <= M; i++) {
		if (scanf("%d%d%d", &T[i], &L[i], &R[i]) != 3) return 1;
	}
	memset(ki_all_set, -1, sizeof(ki_all_set));
	for (i = 1; i <= M; i++) {
		ki_add(1, N + 1, T[i] - T[i - 1]);
		ans += ki_sum(L[i], R[i] + 1);
		ki_set(L[i], R[i] + 1, 0);
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

Submission Info

Judge Result