Submission #348673

#	Time	Username	Problem	Language	Result	Execution time	Memory
348673		Kevin_Zhang_TW	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	870 ms	7532 KiB

xorsum

#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 (stderr)

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8