oj.uz

Submission #227524

# Submission time Handle Problem Language Result Execution time Memory
227524 2020-04-27T16:33:40 Z srvlt Intergalactic ship (IZhO19_xorsum) C++14
83 / 100
 1032 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int N = 1003, M = 100003, K = 128, MOD = 1e9 + 7;
int n, q, a[N], pw[M];
vector <pii> L[N], R[N];
 
int bit[K], mask[K];
 
struct basis {
	vector <short int> b;
	int sz = 0;
	bitset <K> can;
	basis() {
		can[0] = 1;
	}
	void clear() {
		sz = 0;
		b.clear();
		can.reset();
		can[0] = 1;
	};
	void upd() {
		int bsz = b.size();
		can.reset();
		for (int i = 0; i < (1 << bsz); i++) {
			if (i > 0) {
				mask[i] = mask[i ^ (1 << bit[i])] ^ b[bit[i]];
			}
			can[mask[i]] = 1;
		}
	};
	bool add(int x) {
		sz++;
		if (can[x]) {
			return false;
		}
		for (short int i : b) {
			x = min(x, x ^ i);
		}
		b.pb(x);
		upd();
		return true;
	}
	int ways() {
		return pw[sz - (int)b.size()];
	}
};
 
basis cur, C[N][N], A[N][N];
short int f[K][N][N], g[K];
int last[N][N];
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	pw[0] = 1;
	for (int i = 1; i < M; i++) {
		pw[i] = pw[i - 1] * 2 % MOD;
	}
	
	for (int i = 1; i < K; i++) {
		for (int j = 6; j >= 0; j--) {
			if (i >> j & 1) {
				bit[i] = j;
				break;
			}
		}
	}
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		R[r].pb({l, x});
		L[l].pb({r, x});
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		for (int r = n; r >= l; r--) {
			for (auto i : R[r]) {
				if (i.F <= l) {
					cur.add(i.S);
				}
			}
			C[l][r] = cur;
		}
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		last[l][l] = l;
		for (int r = l; r <= n; r++) {
			if (last[l][r] == r) {
				A[l][r] = cur;
				for (int i = 0; i < K; i++) {
					for (int j = 0; j < K; j++) {
						f[i][l][r] += j * cur.can[j ^ i];
					}
				}
			}	else {
				last[l][r] = last[l][r - 1];
			}
			for (auto i : R[r]) {
				if (i.F <= l && cur.add(i.S)) {
					last[l][r + 1] = r + 1;
				}
			}
		}
	}
	int ans = 0;
	for (int r = n; r >= 1; r--) {
		cur.clear();
		for (int i = 0; i < K; i++) {
			g[i] = 0;
			for (int j = 0; j < K; j++) {
				g[i] += j * cur.can[j ^ i];
			}
		}
		for (int l = r; l >= 1; l--) {
			int res = 0, pos = last[l][r];
			for (int i = 0; i < K; i++) {
				res += (int)C[l][r].can[i] * f[i ^ a[l]][l][pos] * g[i ^ a[r]];
				if (res >= MOD) {
					res -= MOD;
				}
			}
			res = (ll)res * C[l][r].ways() % MOD;
			res = (ll)res * A[l][pos].ways() % MOD;
			res = (ll)res * cur.ways() % MOD;
			res = (ll)res * pw[q - C[l][r].sz - A[l][pos].sz - cur.sz] % MOD;
			if (l == r) {
				res = (ll)res * ((MOD + 1) / 2) % MOD;
			}
			int occ = l * (n - r + 1);
			ans += (ll)res * occ % MOD;
			if (ans >= MOD) {
				ans -= MOD;
			}
    		for (auto i : L[l]) {
    			if (i.F >= r && cur.add(i.S)) {
    				for (int k = 0; k < K; k++) {
    					g[k] = 0;
    					for (int j = 0; j < K; j++) {
    						g[k] += j * cur.can[j ^ k];
    					}
    				}
    			}
    		}
    	}
    }
    cout << 2 * ans % MOD;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 96504 KB Output is correct
2 Correct 60 ms 97272 KB Output is correct
3 Correct 66 ms 98552 KB Output is correct
4 Correct 66 ms 98552 KB Output is correct
5 Correct 63 ms 98560 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 96504 KB Output is correct
2 Correct 60 ms 97272 KB Output is correct
3 Correct 66 ms 98552 KB Output is correct
4 Correct 66 ms 98552 KB Output is correct
5 Correct 63 ms 98560 KB Output is correct
6 Correct 103 ms 121592 KB Output is correct
7 Correct 86 ms 121592 KB Output is correct
8 Correct 94 ms 121596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 123768 KB Output is correct
2 Correct 108 ms 121848 KB Output is correct
3 Correct 96 ms 121592 KB Output is correct
4 Correct 91 ms 121592 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 103672 KB Output is correct
2 Correct 72 ms 103672 KB Output is correct
3 Correct 74 ms 103672 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 103672 KB Output is correct
2 Correct 72 ms 103672 KB Output is correct
3 Correct 74 ms 103672 KB Output is correct
4 Correct 80 ms 103928 KB Output is correct
5 Correct 73 ms 103928 KB Output is correct
6 Correct 77 ms 103800 KB Output is correct
7 Correct 75 ms 103800 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 96504 KB Output is correct
2 Correct 60 ms 97272 KB Output is correct
3 Correct 66 ms 98552 KB Output is correct
4 Correct 66 ms 98552 KB Output is correct
5 Correct 63 ms 98560 KB Output is correct
6 Correct 103 ms 121592 KB Output is correct
7 Correct 86 ms 121592 KB Output is correct
8 Correct 94 ms 121596 KB Output is correct
9 Correct 73 ms 103672 KB Output is correct
10 Correct 72 ms 103672 KB Output is correct
11 Correct 74 ms 103672 KB Output is correct
12 Correct 116 ms 121720 KB Output is correct
13 Correct 116 ms 121720 KB Output is correct
14 Correct 112 ms 121592 KB Output is correct
15 Correct 123 ms 121696 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 96504 KB Output is correct
2 Correct 60 ms 97272 KB Output is correct
3 Correct 66 ms 98552 KB Output is correct
4 Correct 66 ms 98552 KB Output is correct
5 Correct 63 ms 98560 KB Output is correct
6 Correct 103 ms 121592 KB Output is correct
7 Correct 86 ms 121592 KB Output is correct
8 Correct 94 ms 121596 KB Output is correct
9 Correct 73 ms 103672 KB Output is correct
10 Correct 72 ms 103672 KB Output is correct
11 Correct 74 ms 103672 KB Output is correct
12 Correct 80 ms 103928 KB Output is correct
13 Correct 73 ms 103928 KB Output is correct
14 Correct 77 ms 103800 KB Output is correct
15 Correct 75 ms 103800 KB Output is correct
16 Correct 116 ms 121720 KB Output is correct
17 Correct 116 ms 121720 KB Output is correct
18 Correct 112 ms 121592 KB Output is correct
19 Correct 123 ms 121696 KB Output is correct
20 Correct 970 ms 230776 KB Output is correct
21 Correct 646 ms 226808 KB Output is correct
22 Correct 1032 ms 231032 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 96504 KB Output is correct
2 Correct 60 ms 97272 KB Output is correct
3 Correct 66 ms 98552 KB Output is correct
4 Correct 66 ms 98552 KB Output is correct
5 Correct 63 ms 98560 KB Output is correct
6 Correct 103 ms 121592 KB Output is correct
7 Correct 86 ms 121592 KB Output is correct
8 Correct 94 ms 121596 KB Output is correct
9 Correct 135 ms 123768 KB Output is correct
10 Correct 108 ms 121848 KB Output is correct
11 Correct 96 ms 121592 KB Output is correct
12 Correct 91 ms 121592 KB Output is correct
13 Runtime error 201 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -