Submission #286974

#TimeUsernameProblemLanguageResultExecution timeMemory
286974oolimryIntergalactic ship (IZhO19_xorsum)C++14
17 / 100
2079 ms3308 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() using namespace std; typedef long long lint; typedef pair<int,int> ii; int arr[1005]; struct query{ int l, r, x; }; vector<query> queries; bool in(int x, int bit){ return ((x & (1 << bit)) != 0); } lint mod = 1000000007; lint two[100005]; lint ans = 0; lint odd(int N){ if(N == 0) return 0; else return two[N-1]; } lint even(int N){ if(N == 0) return 1; else return two[N-1]; } void fix(lint &x){ x %= mod; if(x < 0) x += mod; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); lint n; cin >> n; for(int i = 1;i <= n;i++) cin >> arr[i]; int Q; cin >> Q; for(int q = 0;q < Q;q++){ queries.push_back({}); query &QQ = queries.back(); cin >> QQ.l >> QQ.r >> QQ.x; } two[0] = 1; for(int i = 1;i <= 100004;i++) two[i] = (two[i-1] * 2); for(lint a = 1;a <= n;a++){ for(lint b = 1;b <= n;b++){ for(int aBit = 0;aBit < 7;aBit++){ for(int bBit = 0;bBit < 7;bBit++){ lint none = 0; lint onlyA = 0; lint onlyB = 0; lint both = 0; for(query q : queries){ bool A = false, B = false; int l = q.l, r = q.r, x = q.x; if(in(x, aBit) && l <= a && a <= r) A = true; if(in(x, bBit) && l <= b && b <= r) B = true; if(A && B) both++; else if(A) onlyA++; else if(B) onlyB++; else none++; } //cout << a << " " << b << " " << aBit << " " << bBit << ": " << none << " " << onlyA << " " << onlyB << " " << both << "\n"; ///don't use "both" lint res = two[none] * two[aBit + bBit]; fix(res); res *= min(a,b) * (n - max(a,b) + 1); fix(res); if(in(arr[a], aBit)) res *= even(onlyA); else res *= odd(onlyA); fix(res); if(in(arr[b], bBit)) res *= even(onlyB); else res *= odd(onlyB); fix(res); res *= even(both); fix(res); ans += res; fix(ans); //cout << res << " "; ///use "both" res = two[none] * two[aBit + bBit]; fix(res); res *= min(a,b) * (n - max(a,b) + 1); fix(res); if(in(arr[a], aBit)) res *= odd(onlyA); else res *= even(onlyA); fix(res); if(in(arr[b], bBit)) res *= odd(onlyB); else res *= even(onlyB); fix(res); res *= odd(both); fix(res); ans += res; fix(ans); } } } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...