BZOJ4216 Pig 【分块】
分块+乱搞,内存卡的紧。没卡内存就前缀和水过。
$ysy$就这样把我给带进去了= =。
$TAT$获得成就,$0ms, TLE$
4216 | Time_Limit_Exceed | 0 kb | 0 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; }