oj.uz

Submission #287009

# Submission time Handle Problem Language Result Execution time Memory
287009 2020-08-31T08:55:18 Z oolimry Intergalactic ship (IZhO19_xorsum) C++14
83 / 100
 742 ms 262148 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

int arr[1005];
struct query{ int l, r, x; };

vector<query> queries;

bool in(int x, int bit){
	return ((x & (1 << bit)) != 0);
}

lint mod = 1000000007;
lint two[100005];
lint ans = 0;

inline lint odd(int N){
	if(N == 0) return 0;
	else return two[N-1];
}
inline lint even(int N){
	if(N == 0) return 1;
	else return two[N-1];
}
inline void fix(lint &x){
	x %= mod;
}

lint cnt[7][7][1005][1005];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	lint n; cin >> n;
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	int Q; cin >> Q;
	for(int q = 0;q < Q;q++){
		queries.push_back({});
		query &QQ = queries.back();
		cin >> QQ.l >> QQ.r >> QQ.x;
	}
	
	for(query q : queries){
		int l = q.l, r = q.r, x = q.x;
		for(int bit = 0;bit < 7;bit++){
			for(int bit2 = 0;bit2 < 7;bit2++){	
				if(!in(x, bit) || !in(x, bit2)) continue;
				cnt[bit][bit2][l][r]++;
			}
		}
	}
	
	for(int bit = 0;bit < 7;bit++){
		for(int bit2 = 0;bit2 < 7;bit2++){
			for(int l = 1;l <= n;l++){
				for(int r = n;r >= l;r--){
					cnt[bit][bit2][l][r] += cnt[bit][bit2][l-1][r];
					cnt[bit][bit2][l][r] += cnt[bit][bit2][l][r+1];
					cnt[bit][bit2][l][r] -= cnt[bit][bit2][l-1][r+1];
				}
			}
		}
	}

	two[0] = 1;
	for(int i = 1;i <= 100004;i++) two[i] = (two[i-1] * 2) % mod;

	for(lint a = 1;a <= n;a++){
		for(lint b = a;b <= n;b++){
			for(int aBit = 0;aBit < 7;aBit++){
				for(int bBit = 0;bBit < 7;bBit++){
					lint none = 0;
					lint onlyA = cnt[aBit][aBit][a][a];
					lint onlyB = cnt[bBit][bBit][b][b];
					lint both = cnt[aBit][bBit][a][b];
					onlyA -= both;
					onlyB -= both;
					none = Q - onlyA - onlyB - both;
					
					///don't use "both"
					lint res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					if(in(arr[a], aBit)) res *= even(onlyA);
					else res *= odd(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= even(onlyB);
					else res *= odd(onlyB);
					fix(res);
					
					res *= even(both);
					fix(res);
					
					if(a != b) res *= 2;
					ans += res;
					fix(ans);					
					
					///use "both"
					res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					if(in(arr[a], aBit)) res *= odd(onlyA);
					else res *= even(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= odd(onlyB);
					else res *= even(onlyB);
					fix(res);
					
					res *= odd(both);
					fix(res);
					
					if(a != b) res *= 2;
					ans += res;
					fix(ans);	
				}
			}
		} 
	}
	
	cout << ans << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 28 ms 22912 KB Output is correct
7 Correct 24 ms 22912 KB Output is correct
8 Correct 25 ms 22920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 24168 KB Output is correct
2 Correct 34 ms 23224 KB Output is correct
3 Correct 28 ms 22940 KB Output is correct
4 Correct 25 ms 22912 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 8 ms 7552 KB Output is correct
5 Correct 8 ms 7552 KB Output is correct
6 Correct 8 ms 7552 KB Output is correct
7 Correct 9 ms 7552 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 28 ms 22912 KB Output is correct
7 Correct 24 ms 22912 KB Output is correct
8 Correct 25 ms 22920 KB Output is correct
9 Correct 7 ms 7424 KB Output is correct
10 Correct 7 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 35 ms 22884 KB Output is correct
13 Correct 39 ms 22912 KB Output is correct
14 Correct 29 ms 22912 KB Output is correct
15 Correct 32 ms 22912 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 28 ms 22912 KB Output is correct
7 Correct 24 ms 22912 KB Output is correct
8 Correct 25 ms 22920 KB Output is correct
9 Correct 7 ms 7424 KB Output is correct
10 Correct 7 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 8 ms 7552 KB Output is correct
13 Correct 8 ms 7552 KB Output is correct
14 Correct 8 ms 7552 KB Output is correct
15 Correct 9 ms 7552 KB Output is correct
16 Correct 35 ms 22884 KB Output is correct
17 Correct 39 ms 22912 KB Output is correct
18 Correct 29 ms 22912 KB Output is correct
19 Correct 32 ms 22912 KB Output is correct
20 Correct 742 ms 148840 KB Output is correct
21 Correct 591 ms 149868 KB Output is correct
22 Correct 672 ms 149744 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 28 ms 22912 KB Output is correct
7 Correct 24 ms 22912 KB Output is correct
8 Correct 25 ms 22920 KB Output is correct
9 Correct 68 ms 24168 KB Output is correct
10 Correct 34 ms 23224 KB Output is correct
11 Correct 28 ms 22940 KB Output is correct
12 Correct 25 ms 22912 KB Output is correct
13 Runtime error 251 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -