結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー FF256grhy
提出日時 2015-06-20 18:13:12
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 133 ms / 5,000 ms
コード長 2,324 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 24,704 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 15:20:41
合計ジャッジ時間 1,567 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:16:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:20:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   20 |                 scanf("%d%d%d", &x, &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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