oj.uz

답안 #520112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520112 2022-01-28T12:31:07 Z shmad Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2636 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;
	vt<int> xr(n + 2);
	for (int mask = 0; mask < (1 << q); mask++) {
		fill(all(xr), 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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 13 ms 336 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 12 ms 332 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1412 ms 332 KB Output is correct
2 Correct 1393 ms 336 KB Output is correct
3 Correct 1423 ms 336 KB Output is correct

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1412 ms 332 KB Output is correct
2 Correct 1393 ms 336 KB Output is correct
3 Correct 1423 ms 336 KB Output is correct
4 Incorrect 3 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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 13 ms 336 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 1412 ms 332 KB Output is correct
10 Correct 1393 ms 336 KB Output is correct
11 Correct 1423 ms 336 KB Output is correct
12 Incorrect 52 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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 13 ms 336 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 1412 ms 332 KB Output is correct
10 Correct 1393 ms 336 KB Output is correct
11 Correct 1423 ms 336 KB Output is correct
12 Incorrect 3 ms 468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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 13 ms 336 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Incorrect 17 ms 2636 KB Output isn't correct
10 Halted 0 ms 0 KB -