Submission #70169278

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>
#define BIT_MAX 1123456
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= BIT_MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos++;
  while (pos > 0) {
    sum += bit_table[pos - 1];
    pos -= pos & (-pos);
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define BIT_MAX 1123456

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= BIT_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int N, Q;
int X[212345], Y[212345];

int main(void) {
	int i;
	int cut = 0;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
	}

	for (i = 1; i <= N; i++) {
		bit_add(i, 1);
	}
	for (i = 0; i < Q; i++) {
		if (X[i] > cut) {
			int ans = bit_sum(X[i]) - bit_sum(cut);
			bit_add(Y[i], ans);
			cut = X[i];
			printf("%d\n", ans);
		} else {
			puts("0");
		}
	}

	return 0;
}

Submission Info

Judge Result