oj.uz

Submission #520114

# Submission time Handle Problem Language Result Execution time Memory
520114 2022-01-28T12:33:26 Z shmad Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2628 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast"
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

int n, q, a[N], l[N], r[N], x[N];

bool bit (int x, int i) {
	return (x >> i & 1);
}

int add (int a, int b) {
	a = (a + b);
	if (a < 0) a += mod, a %= mod;
	if (a >= mod) a %= mod;
	return a;
}

int del (int a, int b) {
	a = (a - b);
	if (a < 0) a += mod, a %= mod;
	if (a >= mod) a %= mod;
	return a;
}

int mul (int a, int b) {
	a = (a % mod) * (b % mod);
	if (a < 0) a += mod, a %= mod;
	if (a >= mod) a %= mod;
	return a;
}

void upd (vt<int> v) {
	int xr = 0;
	for (int i = 1; i <= n; i++) xr ^= v[i], a[i] ^= xr;
}

void solve () {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> q;
	for (int i = 0; i < q; i++) cin >> l[i] >> r[i] >> x[i];
	int ans = 0;
	for (int mask = 0; mask < (1 << q); mask++) {
		vt<int> xr(n + 2, 0);
		for (int i = 0; i < q; i++) {
			if (bit(mask, i)) xr[l[i]] ^= x[i], xr[r[i] + 1] ^= x[i];
		}
		upd(xr);
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = i; j <= n; j++) sum += a[j], ans = add(ans, mul(sum, sum));
		}
		upd(xr);
	}
	cout << ans;
	cout << '\n';
}

bool testcases = 0;
                  
signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 13 ms 332 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1475 ms 332 KB Output is correct
2 Correct 1417 ms 340 KB Output is correct
3 Correct 1509 ms 332 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1475 ms 332 KB Output is correct
2 Correct 1417 ms 340 KB Output is correct
3 Correct 1509 ms 332 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 13 ms 332 KB Output is correct
9 Correct 1475 ms 332 KB Output is correct
10 Correct 1417 ms 340 KB Output is correct
11 Correct 1509 ms 332 KB Output is correct
12 Incorrect 50 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 13 ms 332 KB Output is correct
9 Correct 1475 ms 332 KB Output is correct
10 Correct 1417 ms 340 KB Output is correct
11 Correct 1509 ms 332 KB Output is correct
12 Incorrect 2 ms 460 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 13 ms 332 KB Output is correct
9 Incorrect 18 ms 2628 KB Output isn't correct
10 Halted 0 ms 0 KB -