oj.uz

Submission #469646

# Submission time Handle Problem Language Result Execution time Memory
469646 2021-09-01T14:24:52 Z keta_tsimakuridze Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 83 ms 37316 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1e3 + 5, M = 1e5 + 5, mod = 1e9 + 7; // !
int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
vector<pii> q[N];
vector<pair<pii,int> > all;
int choose(int x,int t) {
	return ch[x][t];
}
main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> Q;
	for(int j = 1; j <= Q; j++) {
		int l,r,x;
		cin >> l >> r >> x;
		q[r].push_back({l,x});
		all.push_back({{l,r},x});
	}
	
	ch[0][0] = 1;
	pwr[0] = 1;
	for(int i = 1; i <= Q; i++) {
		for(int t = 0; t < 2; t++){
			ch[i][t] = ch[i - 1][t] + ch[i - 1][1 - t];
			ch[i][t] = ch[i - 1][1 - t] + ch[i - 1][t];
		}
		pwr[i] = pwr[i - 1] * 2 % mod;
	}
	int ans = 0;
	for(int t1 = 0; t1 < 3; t1++) {
		for(int t2 = 0; t2 < 3; t2++) {
			for(int t = 0; t < 3; t++) 
			for(int i = 1; i <= n; i++) {
				p[t][i] = 0;
				for(int j = 1; j <= n; j++) dp[t][i][j] = 0;
			}
			for(int i = 0; i < Q; i++){
				int l = all[i].f.f, r = all[i].f.s, x = all[i].s;
				if((x & (1 << t1)) && (x & (1 << t2))) {
					dp[2][l][r]++;
					p[2][l]++;
					p[2][r + 1]--;
				}
				else if(x & (1 << t1)) dp[0][l][r]++,p[0][l]++, p[0][r + 1]--;
				else if(x & (1 << t2))dp[1][l][r]++, p[1][l]++, p[1][r + 1]--;
			}
			for(int t = 0; t < 3; t++) {
				for(int l = n; l >= 1; l--) {
					for(int r = l; r <= n; r++) dp[t][l][r] += dp[t][l - 1][r] + dp[t][l][r + 1] - dp[t][l - 1][r + 1];
				}
			}
			for(int t = 0; t < 3; t++)
			for(int i = 1; i <= n; i++) {
				p[t][i] += p[t][i - 1];
			}
		
			for(int l = 1; l <= n; l++) {
				for(int r = l; r <= n; r++) {
					int b1 =( (1 << t1) & a[l] ) > 0;
					int b2 = ( (1 << t2) & a[r] ) > 0;
					int P = (1 << t1) % mod * (1 << t2) % mod 
							* l % mod * (n - r + 1) % mod* pwr[Q - p[0][l] - p[1][r] - dp[2][l][r] ] % mod;
					if(l < r) P *= 2;
					
					for(int x1 = 0; x1 < 2; x1++){
						for(int x2 = 0; x2 < 2; x2++) {
							int x3 = 1 ^ x1 ^ b1;
							
							if(x3 ^ x2 ^ b2) {
							//	cout << p[0][l] <<" "<<x1<<" __ "<<p[1][r]<<" "<<x2<<" "<<dp[2][l][r]<<" "<<<<endl;
								ans += choose(p[0][l],x1) % mod * choose(p[1][r],x2) % mod * choose(dp[2][l][r],x3)% mod * P %mod; 
								ans %= mod;
							}
						}
					}
					// 0 0 1 
				}
			}
		}
	}
	cout << ans;
 }

Compilation message

xorsum.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:45:10: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   45 |      dp[2][l][r]++;
      |      ~~~~^
xorsum.cpp:8:50: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                  ^~
xorsum.cpp:45:10: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   45 |      dp[2][l][r]++;
      |      ~~~~^
xorsum.cpp:8:50: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                  ^~
xorsum.cpp:46:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   46 |      p[2][l]++;
      |      ~~~^
xorsum.cpp:8:62: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                              ^
xorsum.cpp:46:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   46 |      p[2][l]++;
      |      ~~~^
xorsum.cpp:8:62: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                              ^
xorsum.cpp:47:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   47 |      p[2][r + 1]--;
      |      ~~~^
xorsum.cpp:8:62: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                              ^
xorsum.cpp:47:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   47 |      p[2][r + 1]--;
      |      ~~~^
xorsum.cpp:8:62: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                              ^
xorsum.cpp:67:71: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   67 |        * l % mod * (n - r + 1) % mod* pwr[Q - p[0][l] - p[1][r] - dp[2][l][r] ] % mod;
      |                                                                   ~~~~^
xorsum.cpp:8:50: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][2],seg[N][2],cnt[N][2],pwr[M],dp[2][N][N],p[2][N];
      |                                                  ^~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 17488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 37316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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

Subtask #8
0 / 30.0

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

Subtask #9
0 / 8.0

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