Submission #384184

#	Time	Username	Problem	Language	Result	Execution time	Memory
384184		patrikpavic2	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1983 ms	204524 KiB

xorsum

#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 (stderr)

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8