oj.uz

Submission #348673

# Submission time Handle Problem Language Result Execution time Memory
348673 2021-01-15T14:19:28 Z Kevin_Zhang_TW Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 870 ms 7532 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T>
bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T>
bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 1005, p = 1e9 + 7, MAX_C = 128, MAX_Q = 100005;

//#define int ll

int n, v[MAX_N], res;

void add(int &a, int b) { a += b - p, a += (a >> 31) & p; }

int q;
vector<tuple<int,int,int>> allq;

int cnt2d[MAX_N][MAX_N], cnt1d[2][MAX_N], up2[MAX_Q]{1};

void putin2d(auto cnt, int mask) {
	memset(cnt, 0, sizeof(cnt2d));
	for (auto [l, r, x] : allq) if ((x & mask) == mask) {
		++cnt[l][l], ++cnt[r+1][r+1];
		--cnt[r+1][l], --cnt[l][r+1];
	}
	for (int i = 1;i <= n;++i) for (int j = 1;j <= n;++j)
		cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];
}
void putin1d(auto cnt, int mask) {
	memset(cnt, 0, sizeof(cnt1d[0]));
	for (auto [l, r, x] : allq) if ((x & mask) == mask) {
		++cnt[l], --cnt[r+1];
	}
	for (int i = 1;i <= n;++i) 
		cnt[i] += cnt[i-1];
}

void addup(int lm, int rm) {
	putin1d(cnt1d[0], lm), putin1d(cnt1d[1], rm);
	putin2d(cnt2d, lm | rm);

	ll mul = lm * rm;
	DE(lm, rm);

	for (int i = 1;i <= n;++i)
		for (int j = i + 1;j <= n;++j) {
			int a = cnt1d[0][i], b = cnt1d[1][j], c = cnt2d[i][j];

			int outside = q - (a + b - c);

			a -= c, b -= c;

			ll i0 = (a == 0 ? 1 : up2[a - 1]), i1 = (a == 0 ? 0 : up2[a - 1]);
			ll j0 = (b == 0 ? 1 : up2[b - 1]), j1 = (b == 0 ? 0 : up2[b - 1]);

			i0 = i0, i1 = i1;
			j0 = j0, j1 = j1;


			if (v[i] & lm) swap(i0, i1);
			if (v[j] & rm) swap(j0, j1);


			int c0 = (c == 0 ? 1 : up2[c - 1]), c1 = (c == 0 ? 0 : up2[c - 1]);

			DE(i, j);

			DE(i0, i1, j0, j1, c0, c1);

			ll ij0 = i0 * j0 % p, ij1 = i1 * j1 % p;

			DE(ij0, c1, '+', ij1, c0, '*', mul);

			ll wei = (up2[outside + 1]) % p * (i * (n - j + 1) * mul % p) % p;

			DE(i, j, wei, mul);

			res = (res + (ij0 * c1 + ij1 * c0) % p * wei) % p;

		}
}

int lstcnt[MAX_C][MAX_N];

void solvesq() {
	for (auto [l, r, x] : allq)
		++lstcnt[x][l], --lstcnt[x][r+1];

	for (int c = 0;c < MAX_C;++c)
		for (int i = 1;i <= n;++i)
			lstcnt[c][i] += lstcnt[c][i-1];

	for (int i = 1;i <= n;++i) {
		int *A = new int[MAX_C]{}, *B = new int[MAX_C]{};

		A[ v[i] ] = 1;

		ll all = q;
		for (int c = 0;c < MAX_C;++c) if (lstcnt[c][i]) {
			fill(B, B + MAX_C, 0);

			all -= lstcnt[c][i];

			ll nw = up2[ lstcnt[c][i] - 1 ];

			for (int x = 0;x < MAX_C;++x)
				add(B[x], A[x] * nw % p), add(B[x ^ c], A[x] * nw % p);

			swap(A, B);
		}
		all = up2[all];

		ll wei = i * (n - i + 1) * all % p;

		for (int c = 0;c < MAX_C;++c) if (A[c]) {
			add(res, wei * (c * c) % p * A[c] % p);
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	cin >> n;

	for (int i = 1;i <= n;++i) 
		cin >> v[i];
	
	cin >> q;

	allq.resize(q);
	for (auto &[l, r, x] : allq)
		cin >> l >> r >> x;

	for (int i = 1;i <= q + 3;++i)
		up2[i] = up2[i-1] * 2 % p;

	for (int lb = 1;lb < MAX_C;lb <<= 1) 
		for (int rb = 1;rb < MAX_C;rb <<= 1)
			addup(lb, rb);

	solvesq();

	cout << res << '\n';
}

Compilation message

xorsum.cpp:39:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   39 | void putin2d(auto cnt, int mask) {
      |              ^~~~
xorsum.cpp:48:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   48 | void putin1d(auto cnt, int mask) {
      |              ^~~~
xorsum.cpp: In function 'void addup(int, int)':
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:62:2: note: in expansion of macro 'DE'
   62 |  DE(lm, rm);
      |  ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:85:4: note: in expansion of macro 'DE'
   85 |    DE(i, j);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:87:4: note: in expansion of macro 'DE'
   87 |    DE(i0, i1, j0, j1, c0, c1);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:91:4: note: in expansion of macro 'DE'
   91 |    DE(ij0, c1, '+', ij1, c0, '*', mul);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:95:4: note: in expansion of macro 'DE'
   95 |    DE(i, j, wei, mul);
      |    ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4844 KB Output is correct
2 Correct 10 ms 4844 KB Output is correct
3 Correct 10 ms 4844 KB Output is correct
4 Correct 10 ms 4844 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4844 KB Output is correct
2 Correct 10 ms 4844 KB Output is correct
3 Correct 10 ms 4844 KB Output is correct
4 Correct 10 ms 4844 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct
6 Correct 18 ms 4972 KB Output is correct
7 Correct 16 ms 4972 KB Output is correct
8 Correct 18 ms 4864 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 6444 KB Output is correct
2 Correct 28 ms 5100 KB Output is correct
3 Correct 17 ms 4972 KB Output is correct
4 Correct 16 ms 4972 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 5868 KB Output is correct
2 Correct 604 ms 5788 KB Output is correct
3 Correct 654 ms 5784 KB Output is correct
4 Correct 592 ms 5868 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4844 KB Output is correct
2 Correct 11 ms 4844 KB Output is correct
3 Correct 11 ms 4844 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4844 KB Output is correct
2 Correct 11 ms 4844 KB Output is correct
3 Correct 11 ms 4844 KB Output is correct
4 Correct 16 ms 4972 KB Output is correct
5 Correct 17 ms 4972 KB Output is correct
6 Correct 16 ms 4972 KB Output is correct
7 Correct 16 ms 4972 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4844 KB Output is correct
2 Correct 10 ms 4844 KB Output is correct
3 Correct 10 ms 4844 KB Output is correct
4 Correct 10 ms 4844 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct
6 Correct 18 ms 4972 KB Output is correct
7 Correct 16 ms 4972 KB Output is correct
8 Correct 18 ms 4864 KB Output is correct
9 Correct 11 ms 4844 KB Output is correct
10 Correct 11 ms 4844 KB Output is correct
11 Correct 11 ms 4844 KB Output is correct
12 Correct 26 ms 4972 KB Output is correct
13 Correct 27 ms 4972 KB Output is correct
14 Correct 17 ms 4972 KB Output is correct
15 Correct 18 ms 4972 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4844 KB Output is correct
2 Correct 10 ms 4844 KB Output is correct
3 Correct 10 ms 4844 KB Output is correct
4 Correct 10 ms 4844 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct
6 Correct 18 ms 4972 KB Output is correct
7 Correct 16 ms 4972 KB Output is correct
8 Correct 18 ms 4864 KB Output is correct
9 Correct 11 ms 4844 KB Output is correct
10 Correct 11 ms 4844 KB Output is correct
11 Correct 11 ms 4844 KB Output is correct
12 Correct 16 ms 4972 KB Output is correct
13 Correct 17 ms 4972 KB Output is correct
14 Correct 16 ms 4972 KB Output is correct
15 Correct 16 ms 4972 KB Output is correct
16 Correct 26 ms 4972 KB Output is correct
17 Correct 27 ms 4972 KB Output is correct
18 Correct 17 ms 4972 KB Output is correct
19 Correct 18 ms 4972 KB Output is correct
20 Correct 363 ms 6828 KB Output is correct
21 Correct 328 ms 6892 KB Output is correct
22 Correct 283 ms 6892 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4844 KB Output is correct
2 Correct 10 ms 4844 KB Output is correct
3 Correct 10 ms 4844 KB Output is correct
4 Correct 10 ms 4844 KB Output is correct
5 Correct 10 ms 4864 KB Output is correct
6 Correct 18 ms 4972 KB Output is correct
7 Correct 16 ms 4972 KB Output is correct
8 Correct 18 ms 4864 KB Output is correct
9 Correct 115 ms 6444 KB Output is correct
10 Correct 28 ms 5100 KB Output is correct
11 Correct 17 ms 4972 KB Output is correct
12 Correct 16 ms 4972 KB Output is correct
13 Correct 617 ms 5868 KB Output is correct
14 Correct 604 ms 5788 KB Output is correct
15 Correct 654 ms 5784 KB Output is correct
16 Correct 592 ms 5868 KB Output is correct
17 Correct 11 ms 4844 KB Output is correct
18 Correct 11 ms 4844 KB Output is correct
19 Correct 11 ms 4844 KB Output is correct
20 Correct 16 ms 4972 KB Output is correct
21 Correct 17 ms 4972 KB Output is correct
22 Correct 16 ms 4972 KB Output is correct
23 Correct 16 ms 4972 KB Output is correct
24 Correct 26 ms 4972 KB Output is correct
25 Correct 27 ms 4972 KB Output is correct
26 Correct 17 ms 4972 KB Output is correct
27 Correct 18 ms 4972 KB Output is correct
28 Correct 363 ms 6828 KB Output is correct
29 Correct 328 ms 6892 KB Output is correct
30 Correct 283 ms 6892 KB Output is correct
31 Correct 870 ms 7468 KB Output is correct
32 Correct 841 ms 7532 KB Output is correct
33 Correct 785 ms 7340 KB Output is correct
34 Correct 789 ms 7404 KB Output is correct
35 Correct 798 ms 7404 KB Output is correct
36 Correct 765 ms 7404 KB Output is correct