oj.uz

Submission #898176

# Submission time Handle Problem Language Result Execution time Memory
898176 2024-01-04T11:13:48 Z vjudge1 Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 4576 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
 // #include "perm.h"
using namespace std;
#define int long long 
const int MOD = 1e9+7;

signed main() {
	int n; cin>>n;
	vector<int> a(n); for(int& i : a) cin>>i;
	vector<tuple<int,int,int>> segs;
	int q; cin>>q;
	for(int i = 0; i<q; i++){
		int l,r,x; cin>>l>>r>>x; l--; r--; 
		segs.push_back({l,r,x});
	}
	int ans = 0;
	for(int i = 0; i < (1<<q); i++){
		vector<int> a1 = a;
		for(int j = 0; j<q; j++){
			if(i & (1<<j)){
				// CAN BE OPTIMIZED USING DIFFERENCE ARRAY
				int l,r,x; tie(l,r,x) = segs[j];
				for(int y = l; y<=r; y++) a1[y]^=x;
			}
			
		}
		vector<int> pre(n+1);
			for(int k= 0; k<n; k++) pre[k+1] = pre[k] + a1[k];
			for(int l = 0; l<n; l++){
				for(int r = l; r < n; r++){
					ans+= (pre[r+1] - pre[l]) * (pre[r+1] - pre[l]);
					ans%=MOD;
				}
			}
	}
	cout<<ans<<endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 436 KB Output is correct
8 Correct 17 ms 348 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 4576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1640 ms 408 KB Output is correct
2 Correct 1644 ms 416 KB Output is correct
3 Correct 1652 ms 344 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1640 ms 408 KB Output is correct
2 Correct 1644 ms 416 KB Output is correct
3 Correct 1652 ms 344 KB Output is correct
4 Incorrect 9 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 436 KB Output is correct
8 Correct 17 ms 348 KB Output is correct
9 Correct 1640 ms 408 KB Output is correct
10 Correct 1644 ms 416 KB Output is correct
11 Correct 1652 ms 344 KB Output is correct
12 Incorrect 70 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 436 KB Output is correct
8 Correct 17 ms 348 KB Output is correct
9 Correct 1640 ms 408 KB Output is correct
10 Correct 1644 ms 416 KB Output is correct
11 Correct 1652 ms 344 KB Output is correct
12 Incorrect 9 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 436 KB Output is correct
8 Correct 17 ms 348 KB Output is correct
9 Incorrect 38 ms 4576 KB Output isn't correct
10 Halted 0 ms 0 KB -