oj.uz

Submission #469655

# Submission time Handle Problem Language Result Execution time Memory
469655 2021-09-01T14:33:43 Z keta_tsimakuridze Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 71 ms 37180 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],pwr[M],dp[2][N][N],p[2][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;
		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] %= mod;
		}
		pwr[i] = pwr[i - 1] * 2 % mod;
	}
	int ans = 0;
	for(int t1 = 0; t1 < 8; t1++) {
		for(int t2 = 0; t2 < 8; 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 = 1; l <= n; l++) {
					for(int r = n; r >= 1; 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;
					P %= mod;
					for(int x1 = 0; x1 < 2; x1++){
						for(int x2 = 0; x2 < 2; x2++) {
							int x3 = 1 ^ x1 ^ b1;
							
							if(x3 ^ x2 ^ b2) {
								ans += choose(p[0][l],x1) % mod * choose(p[1][r],x2) % mod * choose(dp[2][l][r],x3)% mod * P %mod; 
								ans %= mod;
							}
						}
					}
				}
			}
		}
	}
	cout << ans;
 }

Compilation message

xorsum.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:43:10: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   43 |      dp[2][l][r]++;
      |      ~~~~^
xorsum.cpp:8:30: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                              ^~
xorsum.cpp:43:10: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   43 |      dp[2][l][r]++;
      |      ~~~~^
xorsum.cpp:8:30: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                              ^~
xorsum.cpp:44:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   44 |      p[2][l]++;
      |      ~~~^
xorsum.cpp:8:42: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                                          ^
xorsum.cpp:44:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   44 |      p[2][l]++;
      |      ~~~^
xorsum.cpp:8:42: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                                          ^
xorsum.cpp:45:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   45 |      p[2][r + 1]--;
      |      ~~~^
xorsum.cpp:8:42: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                                          ^
xorsum.cpp:45:9: warning: array subscript 2 is above array bounds of 'long long int [2][1005]' [-Warray-bounds]
   45 |      p[2][r + 1]--;
      |      ~~~^
xorsum.cpp:8:42: note: while referencing 'p'
    8 | int a[N],n,Q,ch[M][2],pwr[M],dp[2][N][N],p[2][N];
      |                                          ^
xorsum.cpp:65:71: warning: array subscript 2 is above array bounds of 'long long int [2][1005][1005]' [-Warray-bounds]
   65 |        * l % mod * (n - r + 1) % mod* pwr[Q - p[0][l] - p[1][r] - dp[2][l][r] ] % mod;
      |                                                                   ~~~~^
xorsum.cpp:8:30: note: while referencing 'dp'
    8 | int a[N],n,Q,ch[M][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 71 ms 12084 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 30 ms 37180 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 -