oj.uz

Submission #384184

# Submission time Handle Problem Language Result Execution time Memory
384184 2021-03-31T16:46:10 Z patrikpavic2 Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 1983 ms 204524 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e3 + 50;
const int Q = 1e5 + 500;
const int BIT = 7;
const int MOD = 1e9 + 7;

inline int add(int A, int B){
	if(A + B >= MOD)
		return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B){
	if(A - B < 0)
		return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

int pres[BIT][BIT][N][N];
int cnt[BIT][N], n, q, niz[N];

void dodaj(int l, int r, int x){
	for(int i = 0;i < BIT;i++){
		if(!(x & (1 << i))) continue;
		cnt[i][l]++; cnt[i][r + 1]--;
		for(int j = 0;j < BIT;j++){
			if(!(x & (1 << j))) continue;
			pres[i][j][l][l]++;
			pres[i][j][r + 1][r + 1]++;
			pres[i][j][l][r + 1]--;
			pres[i][j][r + 1][l]--;
		}
	}
}

int pot[Q], par[Q], nep[Q];

int calc(int i, int j, int x, int y){
	int A = pres[x][y][i][j];
	int B = cnt[x][i] - A, C = cnt[y][j] - A;
	int ii = !!(niz[i] & (1 << x)), jj = !!(niz[j] & (1 << y));
	//if(A || B || C) {
	//	printf("Q : %d %d %d %d\n", i, j, x, y);
	//	printf("q = %d A = %d B = %d C = %d\n", q, A, B, C);
	//}
	if(!ii && !jj)
		return mul(pot[q - A - B - C], add(mul(par[A], mul(nep[B], nep[C])), mul(nep[A], mul(par[B], par[C]))));
	if(ii && jj){
		//printf("%d * (%d * %d * %d + %d * %d * %d)\n", pot[q - A - B - C], par[A], par[B], par[C], nep[A], nep[B], nep[C]);
		return mul(pot[q - A - B - C], add(mul(par[A], mul(par[B], par[C])), mul(nep[A], mul(nep[B], nep[C]))));
	}
	if(!ii && jj)
		return mul(pot[q - A - B - C], add(mul(par[A], mul(nep[B], par[C])), mul(nep[A], mul(par[B], nep[C]))));
	if(ii && !jj)
		return mul(pot[q - A - B - C], add(mul(par[A], mul(par[B], nep[C])), mul(nep[A], mul(nep[B], par[C]))));

}

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d", niz + i);
	scanf("%d", &q);
	for(int b = 0;b < q;b++){
		int l, r, x; scanf("%d%d%d", &l, &r, &x);
		dodaj(l, r, x);
	}
	pot[0] = 1;
	for(int i = 1;i < Q;i++)
		pot[i] = add(pot[i - 1], pot[i - 1]);
	for(int i = 0;i + 1 < Q;i++)
		par[i + 1] = pot[i], nep[i + 1] = pot[i];
	par[0] = 1;
	for(int j = 0;j < BIT;j++)
		for(int i = 1;i <= n;i++)
			cnt[j][i] += cnt[j][i - 1];
	for(int a = 0;a < BIT;a++){
		for(int b = 0;b < BIT;b++){
			for(int i = 1;i <= n;i++)
				for(int j = 1;j <= n;j++)
					pres[a][b][i][j] += pres[a][b][i][j - 1];
			for(int i = 1;i <= n;i++)
				for(int j = 1;j <= n;j++)
					pres[a][b][i][j] += pres[a][b][i - 1][j];
						
		}
	}
	int sol = 0;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			for(int a = 0;a < BIT;a++)
				for(int b = 0;b < BIT;b++){
					int ret = calc(i, j, a, b);
					//if(ret) printf("i = %d j = %d a = %d b = %d ret = %d\n", i, j, a, b, ret);
					int ukol = (min(i, j)) * (n - max(i, j) + 1);
					sol = add(sol, mul(mul(pot[a + b], ukol), ret));
				}
	printf("%d\n", sol);
	return 0;
}

Compilation message

xorsum.cpp: In function 'int calc(int, int, int, int)':
xorsum.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^
xorsum.cpp: In function 'int main()':
xorsum.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
xorsum.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d", niz + i);
      |   ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
xorsum.cpp:76:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   int l, r, x; scanf("%d%d%d", &l, &r, &x);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 34 ms 21888 KB Output is correct
7 Correct 33 ms 21868 KB Output is correct
8 Correct 35 ms 21908 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 22764 KB Output is correct
2 Correct 36 ms 21996 KB Output is correct
3 Correct 32 ms 21868 KB Output is correct
4 Correct 33 ms 21996 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1713 ms 203388 KB Output is correct
2 Correct 1700 ms 203244 KB Output is correct
3 Correct 1703 ms 203116 KB Output is correct
4 Correct 1683 ms 203116 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

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

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 34 ms 21888 KB Output is correct
7 Correct 33 ms 21868 KB Output is correct
8 Correct 35 ms 21908 KB Output is correct
9 Correct 8 ms 7788 KB Output is correct
10 Correct 8 ms 7788 KB Output is correct
11 Correct 7 ms 7788 KB Output is correct
12 Correct 31 ms 21996 KB Output is correct
13 Correct 31 ms 22124 KB Output is correct
14 Correct 32 ms 21868 KB Output is correct
15 Correct 35 ms 22016 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 34 ms 21888 KB Output is correct
7 Correct 33 ms 21868 KB Output is correct
8 Correct 35 ms 21908 KB Output is correct
9 Correct 8 ms 7788 KB Output is correct
10 Correct 8 ms 7788 KB Output is correct
11 Correct 7 ms 7788 KB Output is correct
12 Correct 9 ms 7916 KB Output is correct
13 Correct 9 ms 7916 KB Output is correct
14 Correct 9 ms 7916 KB Output is correct
15 Correct 9 ms 7916 KB Output is correct
16 Correct 31 ms 21996 KB Output is correct
17 Correct 31 ms 22124 KB Output is correct
18 Correct 32 ms 21868 KB Output is correct
19 Correct 35 ms 22016 KB Output is correct
20 Correct 593 ms 103788 KB Output is correct
21 Correct 537 ms 103820 KB Output is correct
22 Correct 569 ms 103788 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 34 ms 21888 KB Output is correct
7 Correct 33 ms 21868 KB Output is correct
8 Correct 35 ms 21908 KB Output is correct
9 Correct 72 ms 22764 KB Output is correct
10 Correct 36 ms 21996 KB Output is correct
11 Correct 32 ms 21868 KB Output is correct
12 Correct 33 ms 21996 KB Output is correct
13 Correct 1713 ms 203388 KB Output is correct
14 Correct 1700 ms 203244 KB Output is correct
15 Correct 1703 ms 203116 KB Output is correct
16 Correct 1683 ms 203116 KB Output is correct
17 Correct 8 ms 7788 KB Output is correct
18 Correct 8 ms 7788 KB Output is correct
19 Correct 7 ms 7788 KB Output is correct
20 Correct 9 ms 7916 KB Output is correct
21 Correct 9 ms 7916 KB Output is correct
22 Correct 9 ms 7916 KB Output is correct
23 Correct 9 ms 7916 KB Output is correct
24 Correct 31 ms 21996 KB Output is correct
25 Correct 31 ms 22124 KB Output is correct
26 Correct 32 ms 21868 KB Output is correct
27 Correct 35 ms 22016 KB Output is correct
28 Correct 593 ms 103788 KB Output is correct
29 Correct 537 ms 103820 KB Output is correct
30 Correct 569 ms 103788 KB Output is correct
31 Correct 1953 ms 204416 KB Output is correct
32 Correct 1802 ms 204524 KB Output is correct
33 Correct 1913 ms 204344 KB Output is correct
34 Correct 1983 ms 204296 KB Output is correct
35 Correct 1979 ms 204176 KB Output is correct
36 Correct 1953 ms 204348 KB Output is correct