oj.uz

Submission #348669

# Submission time Handle Problem Language Result Execution time Memory
348669 2021-01-15T14:18:39 Z Kevin_Zhang_TW Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 938 ms 15596 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 MAX_C 4

#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:41:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   41 | void putin2d(auto cnt, int mask) {
      |              ^~~~
xorsum.cpp:50:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   50 | void putin1d(auto cnt, int mask) {
      |              ^~~~
xorsum.cpp: In function 'void addup(ll, ll)':
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:64:2: note: in expansion of macro 'DE'
   64 |  DE(lm, rm);
      |  ^~
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(i, j);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:89:4: note: in expansion of macro 'DE'
   89 |    DE(i0, i1, j0, j1, c0, c1);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:93:4: note: in expansion of macro 'DE'
   93 |    DE(ij0, c1, '+', ij1, c0, '*', mul);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:97:4: note: in expansion of macro 'DE'
   97 |    DE(i, j, wei, mul);
      |    ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8812 KB Output is correct
2 Correct 44 ms 8812 KB Output is correct
3 Correct 48 ms 8812 KB Output is correct
4 Correct 43 ms 8812 KB Output is correct
5 Correct 43 ms 8812 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8812 KB Output is correct
2 Correct 44 ms 8812 KB Output is correct
3 Correct 48 ms 8812 KB Output is correct
4 Correct 43 ms 8812 KB Output is correct
5 Correct 43 ms 8812 KB Output is correct
6 Correct 49 ms 9068 KB Output is correct
7 Correct 53 ms 9100 KB Output is correct
8 Correct 56 ms 9216 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 12140 KB Output is correct
2 Correct 63 ms 9452 KB Output is correct
3 Correct 56 ms 9068 KB Output is correct
4 Correct 52 ms 9196 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 11372 KB Output is correct
2 Correct 605 ms 11372 KB Output is correct
3 Correct 607 ms 11372 KB Output is correct
4 Correct 604 ms 11372 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8812 KB Output is correct
2 Correct 49 ms 8812 KB Output is correct
3 Correct 47 ms 8812 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8812 KB Output is correct
2 Correct 49 ms 8812 KB Output is correct
3 Correct 47 ms 8812 KB Output is correct
4 Correct 50 ms 9068 KB Output is correct
5 Correct 52 ms 9068 KB Output is correct
6 Correct 54 ms 9068 KB Output is correct
7 Correct 53 ms 9068 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8812 KB Output is correct
2 Correct 44 ms 8812 KB Output is correct
3 Correct 48 ms 8812 KB Output is correct
4 Correct 43 ms 8812 KB Output is correct
5 Correct 43 ms 8812 KB Output is correct
6 Correct 49 ms 9068 KB Output is correct
7 Correct 53 ms 9100 KB Output is correct
8 Correct 56 ms 9216 KB Output is correct
9 Correct 44 ms 8812 KB Output is correct
10 Correct 49 ms 8812 KB Output is correct
11 Correct 47 ms 8812 KB Output is correct
12 Correct 56 ms 9068 KB Output is correct
13 Correct 55 ms 9068 KB Output is correct
14 Correct 48 ms 9196 KB Output is correct
15 Correct 54 ms 9196 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8812 KB Output is correct
2 Correct 44 ms 8812 KB Output is correct
3 Correct 48 ms 8812 KB Output is correct
4 Correct 43 ms 8812 KB Output is correct
5 Correct 43 ms 8812 KB Output is correct
6 Correct 49 ms 9068 KB Output is correct
7 Correct 53 ms 9100 KB Output is correct
8 Correct 56 ms 9216 KB Output is correct
9 Correct 44 ms 8812 KB Output is correct
10 Correct 49 ms 8812 KB Output is correct
11 Correct 47 ms 8812 KB Output is correct
12 Correct 50 ms 9068 KB Output is correct
13 Correct 52 ms 9068 KB Output is correct
14 Correct 54 ms 9068 KB Output is correct
15 Correct 53 ms 9068 KB Output is correct
16 Correct 56 ms 9068 KB Output is correct
17 Correct 55 ms 9068 KB Output is correct
18 Correct 48 ms 9196 KB Output is correct
19 Correct 54 ms 9196 KB Output is correct
20 Correct 400 ms 14444 KB Output is correct
21 Correct 355 ms 14444 KB Output is correct
22 Correct 308 ms 14444 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8812 KB Output is correct
2 Correct 44 ms 8812 KB Output is correct
3 Correct 48 ms 8812 KB Output is correct
4 Correct 43 ms 8812 KB Output is correct
5 Correct 43 ms 8812 KB Output is correct
6 Correct 49 ms 9068 KB Output is correct
7 Correct 53 ms 9100 KB Output is correct
8 Correct 56 ms 9216 KB Output is correct
9 Correct 145 ms 12140 KB Output is correct
10 Correct 63 ms 9452 KB Output is correct
11 Correct 56 ms 9068 KB Output is correct
12 Correct 52 ms 9196 KB Output is correct
13 Correct 613 ms 11372 KB Output is correct
14 Correct 605 ms 11372 KB Output is correct
15 Correct 607 ms 11372 KB Output is correct
16 Correct 604 ms 11372 KB Output is correct
17 Correct 44 ms 8812 KB Output is correct
18 Correct 49 ms 8812 KB Output is correct
19 Correct 47 ms 8812 KB Output is correct
20 Correct 50 ms 9068 KB Output is correct
21 Correct 52 ms 9068 KB Output is correct
22 Correct 54 ms 9068 KB Output is correct
23 Correct 53 ms 9068 KB Output is correct
24 Correct 56 ms 9068 KB Output is correct
25 Correct 55 ms 9068 KB Output is correct
26 Correct 48 ms 9196 KB Output is correct
27 Correct 54 ms 9196 KB Output is correct
28 Correct 400 ms 14444 KB Output is correct
29 Correct 355 ms 14444 KB Output is correct
30 Correct 308 ms 14444 KB Output is correct
31 Correct 938 ms 15476 KB Output is correct
32 Correct 822 ms 15596 KB Output is correct
33 Correct 792 ms 15468 KB Output is correct
34 Correct 806 ms 15340 KB Output is correct
35 Correct 807 ms 15340 KB Output is correct
36 Correct 798 ms 15340 KB Output is correct