BZOJ4216 Pig 【分块】

tonyfang posted @ 2015年8月28日 17:43 in BZOJ with tags c++ OI , 307 阅读

分块+乱搞,内存卡的紧。没卡内存就前缀和水过。

$ysy$就这样把我给带进去了= =。

$TAT$获得成就,$0ms, TLE$

 

4216 Time_Limit_Exceed kb ms C++ 948 B

后来知道,BZOJ好像把TLE和MLE搞反了还是什么的。。数组开太大了。。

一怒之下用了动态分配。

 

# include <stdio.h>
# include <algorithm>
using namespace std;

long long *f, l, r, lastans;
int *a;
int n, m, t;

inline long long mabs(long long a) {
	return a > 0 ? a : -a;
}

// get [1,i]
inline long long g(int x) {
	int tonum = x / 20;
	long long res = 0;
	for (int i = tonum * 20 + 1; i <= x; ++i) res += a[i];
	return res + f[tonum];
}

int main() {
	scanf("%d %d %d", &n, &m, &t);
	a = new int[n+1];
	f = new long long[(n+1)/20+1];
	long long c = 0;
	for (int i=1; i<=n; ++i) {
		scanf("%d", &a[i]);
		c += a[i];
		if (i % 20 == 0) f[i / 20] = c;
	}
	for (int i=1; i<=m; ++i) {
		scanf("%lld %lld", &l, &r);
		if (t) {
			l = l ^ lastans; l = l % n + 1;
			r = r ^ lastans; r = r % n + 1;
		}
		if (l > r) swap(l, r);
		lastans = g(r) - g(l - 1);
		printf("%lld\n", lastans); 
		lastans = mabs(lastans);
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter