oj.uz

답안 #354244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
354244 2021-01-21T15:31:58 Z cheissmart Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 234 ms 262148 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 9, N = 1003, M = 1e9 + 7, K = 7;

int a[N], pw[100005];
int cnt[N][N][K][K][3];
// 0 -> 0 1
// 1 -> 1 0
// 2 -> 1 1

void add(int& a, int b) {
	a += b;
	if(a >= M) a -= M;
}

signed main()
{
	IO_OP;

	pw[0] = 1;
	for(int i = 1; i < 100005; i++)
		pw[i] = pw[i - 1] * 2 % M;

	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		for(int bit1 = 0; bit1 < K; bit1++) {
			for(int bit2 = 0; bit2 < K; bit2++) {
				int t1 = x >> bit1 & 1, t2 = x >> bit2 & 1;
				if(t1 == 0 && t2 == 0) continue;
				int which = t1 * 2 + t2 - 1;
				cnt[l][l][bit1][bit2][which]++;
				cnt[l][r + 1][bit1][bit2][which]--;
				cnt[r + 1][l][bit1][bit2][which]--;
				cnt[r + 1][r + 1][bit1][bit2][which]++;
			} 
		}
	}
	// TODO: change for loop order and see time
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int bit1 = 0; bit1 < K; bit1++) {
				for(int bit2 = 0; bit2 < K; bit2++) {
					for(int which = 0; which < 3; which++)
						cnt[i][j][bit1][bit2][which] += cnt[i - 1][j][bit1][bit2][which] +
					 									cnt[i][j - 1][bit1][bit2][which] -
					 									cnt[i - 1][j - 1][bit1][bit2][which];
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			int occ = i * (n - j + 1);
			for(int bit1 = 0; bit1 < K; bit1++) {
				for(int bit2 = 0; bit2 < K; bit2++) {
					int mul = (ll) (occ << (bit1 + bit2)) % M;
					if(i < j) mul = mul * 2 % M;
					int c01 = cnt[i][j][bit1][bit2][0];
					int c10 = cnt[i][j][bit1][bit2][1];
					int c11 = cnt[i][j][bit1][bit2][2];
					int c00 = q - c01 - c10 - c11;
					int tt = 0;
					int ways00 = 1, ways11 = 1;
					int t1 = a[i] >> bit1 & 1, t2 = a[j] >> bit2 & 1;
					if(t1 == 0 && t2 == 0) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;

						if(c01 == 0 || c10 == 0) ways11 = 0;
						else {
							ways11 = (ll) ways11 * pw[c01 - 1] % M;
							ways11 = (ll) ways11 * pw[c10 - 1] % M;
						}
					} else if(t1 == 1 && t2 == 1) {
						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;

						if(c01 == 0 || c10 == 0) ways00 = 0;
						else {
							ways00 = (ll) ways00 * pw[c01 - 1] % M;
							ways00 = (ll) ways00 * pw[c10 - 1] % M;
						}
					} else if(t1 == 1 && t2 == 0) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;

						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
						else ways00 = 0;

						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						else ways11 = 0;

						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
					} else if(t1 == 0 && t2 == 1) {
						if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
						else ways00 = 0;

						if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;

						if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
						
						if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
						else ways11 = 0;
					} else throw;
					if(c00) add(tt, (ll) ways11 * pw[c00 - 1] % M);
					else add(tt, ways11);
					if(c11) add(tt, (ll) ways00 * pw[c11 - 1] % M);
					tt = (ll) tt * pw[c00] % M;
					add(ans, (ll) tt * mul % M);
				}
			}
		}
	}
	cout << ans << endl;

}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 7764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 234 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -