oj.uz

답안 #348662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348662 2021-01-15T14:11:58 Z Kevin_Zhang_TW Intergalactic ship (IZhO19_xorsum) C++17
4 / 100
 508 ms 7280 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

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);

//			if (v[i] & lm) assert(i1 == 1);
//			if (v[j] & rm) assert(j1 == 1);

			//assert(i0 + i1 == 1 && j0 + j1 == 1);

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

			//assert(c0 == 1 && c1 == 0);

			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] * 2ll * i * (n - j + 1) * mul % p;

			DE(i, j, wei, mul);

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

		}
	res %= 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]) {
			all -= lstcnt[c][i];
			fill(B, B + MAX_C, 0);
			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) * 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;++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:91:4: note: in expansion of macro 'DE'
   91 |    DE(i, j);
      |    ^~
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(i0, i1, j0, j1, c0, c1);
      |    ^~
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(ij0, c1, '+', ij1, c0, '*', mul);
      |    ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
xorsum.cpp:101:4: note: in expansion of macro 'DE'
  101 |    DE(i, j, wei, mul);
      |    ^~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 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 4844 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 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 4844 KB Output is correct
6 Incorrect 16 ms 4972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 7280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 508 ms 5868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 4844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 4844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 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 4844 KB Output is correct
6 Incorrect 16 ms 4972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 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 4844 KB Output is correct
6 Incorrect 16 ms 4972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 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 4844 KB Output is correct
6 Incorrect 16 ms 4972 KB Output isn't correct
7 Halted 0 ms 0 KB -