結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー FF256grhyFF256grhy
提出日時 2015-06-20 18:13:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 144 ms / 5,000 ms
コード長 2,324 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 27,220 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-21 22:11:19
合計ジャッジ時間 1,901 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 27 ms
4,380 KB
testcase_10 AC 28 ms
4,376 KB
testcase_11 AC 19 ms
4,376 KB
testcase_12 AC 27 ms
4,380 KB
testcase_13 AC 7 ms
4,376 KB
testcase_14 AC 65 ms
4,380 KB
testcase_15 AC 144 ms
4,376 KB
testcase_16 AC 110 ms
4,380 KB
testcase_17 AC 57 ms
4,380 KB
testcase_18 AC 88 ms
4,376 KB
testcase_19 AC 43 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

int n, q;
int array[391][256], sum[391][3], mono_flag[391];
long long int a, b;
int memo_a, memo_b;

void spray(int, int, int);
void spray_full(int, int);
void spray_part(int, int, int, int);
void count(int, int, int);
void count_full(int);
void count_part(int, int, int);

int main(void) {
	scanf("%d%d", &n, &q);
	int i;
	for(i = 0; i < q; i++) {
		int x, l, r;
		scanf("%d%d%d", &x, &l, &r);
		if(x) { spray(x, l, r); } else { count(l, r, 0); }
	}
	count(0, n - 1, 1);
	printf("%lld %lld\n", a, b);
	return 0;
}

void spray(int x, int l, int r) {
	int dl = l / 256, dr = r / 256;
	int ml = l % 256, mr = r % 256;
	
	if(dl == dr) {
		spray_part(x, dl, ml, mr);
	} else {
		int i;
		spray_part(x, dl, ml, 255);
		spray_part(x, dr,  0,  mr);
		for(i = dl + 1; i <= dr - 1; i++) { spray_full(x, i); }
	}
	return;
}

void spray_full(int x, int p) {
	sum[p][0] = 0;
	sum[p][1] = 0;
	sum[p][2] = 0;
	sum[p][x] = 256;
	mono_flag[p] = x;
	return;
}

void spray_part(int x, int p, int l, int r) {
	if(l == 0 && r == 255) { spray_full(x, p); return; }
	
	int i;
	if(mono_flag[p] != -1) {
		sum[p][0] = 0;
		sum[p][1] = 0;
		sum[p][2] = 0;
		sum[p][x] = r - l + 1;
		sum[p][ mono_flag[p] ] += 256 - (r - l + 1);
		for(i = 0; i < 256; i++) {
			array[p][i] = (l <= i&& i <= r) ? x : mono_flag[p];
		}
		mono_flag[p] = -1;
	} else {
		for(i = l; i <= r; i++) {
			sum[p][ array[p][i] ]--;
			sum[p][ x           ]++;
			array[p][i] = x;
 		}
	}
	return;
}

void count(int l, int r, int is_last) {
	memo_a = 0;
	memo_b = 0;
	int dl = l / 256, dr = r / 256;
	int ml = l % 256, mr = r % 256;
	
	if(dl == dr) {
		count_part(dl, ml, mr);
	} else {
		int i;
		count_part(dl, ml, 255);
		count_part(dr,  0,  mr);
		for(i = dl + 1; i <= dr - 1; i++) { count_full(i); }
	}
	
	if(memo_a > memo_b || is_last) { a += memo_a; } 
	if(memo_a < memo_b || is_last) { b += memo_b; }
	
	return;
}

void count_full(int p) {
	memo_a += sum[p][1];
	memo_b += sum[p][2];
	return;
}

void count_part(int p, int l, int r) {
	if(l == 0 && r == 255) { count_full(p); return; }
	int i;
	if(mono_flag[p] != -1) {
		if(mono_flag[p] == 1) { memo_a += r - l + 1; }
		if(mono_flag[p] == 2) { memo_b += r - l + 1; }
	} else {
		for(i = l; i <= r; i++) {
			if(array[p][i] == 1) { memo_a++; }
			if(array[p][i] == 2) { memo_b++; }
 		}
	}
	return;
}
0