oj.uz

Submission #382136

# Submission time Handle Problem Language Result Execution time Memory
382136 2021-03-26T13:11:27 Z vanic Intergalactic ship (IZhO19_xorsum) C++14
47 / 100
 2000 ms 262148 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
#include <bitset>

using namespace std;

typedef long long ll;

const int maxn=1005, mod=1e9+7, maxq=1e5+5, Log=7;

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

inline int mul(int a, int b){
	return (ll)a*b%mod;
}

int n, m;
int a[maxn];
int sol;
int q[maxq][3];
int komb[maxn][maxn][Log][Log][2][2];

void precompute(){
	bool p1, p2;
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			for(int k=0; k<Log; k++){
				for(int l=0; l<Log; l++){
					p1=a[i]&(1<<k);
					p2=a[j]&(1<<l);
					komb[i][j][k][l][p1][p2]=1;
				}
			}
		}
	}
	for(int qq=0; qq<m; qq++){
		for(int i=0; i<n; i++){
			for(int j=i; j<n; j++){
				for(int k=0; k<Log; k++){
					for(int l=0; l<Log; l++){
						if(q[qq][0]<=i && q[qq][1]>=i && q[qq][0]<=j && q[qq][1]>=j && (1<<k)&q[qq][2] && (1<<l)&q[qq][2]){
							komb[i][j][k][l][0][0]=sum(komb[i][j][k][l][0][0], komb[i][j][k][l][1][1]);
							komb[i][j][k][l][0][1]=sum(komb[i][j][k][l][0][1], komb[i][j][k][l][1][0]);
							komb[i][j][k][l][1][0]=komb[i][j][k][l][0][1];
							komb[i][j][k][l][1][1]=komb[i][j][k][l][0][0];
							
						}
						else if(q[qq][0]<=i && q[qq][1]>=i && (1<<k)&q[qq][2]){
							komb[i][j][k][l][0][0]=sum(komb[i][j][k][l][0][0], komb[i][j][k][l][1][0]);
							komb[i][j][k][l][0][1]=sum(komb[i][j][k][l][0][1], komb[i][j][k][l][1][1]);
							komb[i][j][k][l][1][0]=komb[i][j][k][l][0][0];
							komb[i][j][k][l][1][1]=komb[i][j][k][l][0][1];
						}
						else if(q[qq][0]<=j && q[qq][1]>=j && (1<<l)&q[qq][2]){
							komb[i][j][k][l][0][0]=sum(komb[i][j][k][l][0][0], komb[i][j][k][l][0][1]);
							komb[i][j][k][l][0][1]=komb[i][j][k][l][0][0];
							komb[i][j][k][l][1][0]=sum(komb[i][j][k][l][1][0], komb[i][j][k][l][1][1]);
							komb[i][j][k][l][1][1]=komb[i][j][k][l][1][0];
						}
						else{
							komb[i][j][k][l][0][0]=mul(komb[i][j][k][l][0][0], 2);
							komb[i][j][k][l][0][1]=mul(komb[i][j][k][l][0][1], 2);
							komb[i][j][k][l][1][0]=mul(komb[i][j][k][l][1][0], 2);
							komb[i][j][k][l][1][1]=mul(komb[i][j][k][l][1][1], 2);
						}
					}
				}
			}
		}
	}
}

void rijesi(){
	int kofa;
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			if(i!=j){
				kofa=2*(i+1)*(n-j);
			}
			else{
				kofa=(i+1)*(n-j);
			}
			for(int k=0; k<Log; k++){
				for(int l=0; l<Log; l++){
					sol=sum(sol, mul(mul(1<<(k+l), kofa), komb[i][j][k][l][1][1]));
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> q[i][0] >> q[i][1] >> q[i][2];
		q[i][0]--;
		q[i][1]--;
	}
	precompute();
/*	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			for(int k=0; k<2; k++){
				for(int l=0; l<2; l++){
					cout << komb[i][j][k][l][1][1] << ' ';
				}
				cout << '\n';
			}
			cout << '\n';
		}
		cout << '\n';
	}*/
	rijesi();
	cout << sol <<  '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 26 ms 4716 KB Output is correct
7 Correct 29 ms 4716 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 5868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 868 ms 988 KB Output is correct
5 Correct 867 ms 1004 KB Output is correct
6 Correct 864 ms 988 KB Output is correct
7 Correct 838 ms 1004 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 26 ms 4716 KB Output is correct
7 Correct 29 ms 4716 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct
9 Correct 5 ms 876 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 5 ms 876 KB Output is correct
12 Correct 553 ms 4716 KB Output is correct
13 Correct 533 ms 4844 KB Output is correct
14 Correct 568 ms 4716 KB Output is correct
15 Correct 595 ms 4844 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 26 ms 4716 KB Output is correct
7 Correct 29 ms 4716 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct
9 Correct 5 ms 876 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 5 ms 876 KB Output is correct
12 Correct 868 ms 988 KB Output is correct
13 Correct 867 ms 1004 KB Output is correct
14 Correct 864 ms 988 KB Output is correct
15 Correct 838 ms 1004 KB Output is correct
16 Correct 553 ms 4716 KB Output is correct
17 Correct 533 ms 4844 KB Output is correct
18 Correct 568 ms 4716 KB Output is correct
19 Correct 595 ms 4844 KB Output is correct
20 Execution timed out 2085 ms 100204 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 26 ms 4716 KB Output is correct
7 Correct 29 ms 4716 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct
9 Execution timed out 2079 ms 5868 KB Time limit exceeded
10 Halted 0 ms 0 KB -