제출 #142963

#제출 시각아이디문제언어결과실행 시간메모리
142963BenqIntergalactic ship (IZhO19_xorsum)C++14
100 / 100
556 ms192316 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) for (int i = 0; i < (a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define trav(a, x) for (auto& a : x) #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define sz(x) (int)x.size() #define beg(x) x.begin() #define en(x) x.end() #define all(x) beg(x), en(x) #define resz resize const int MOD = 1000000007; // 998244353 const ll INF = 1e18; const int MX = 100001; const ld PI = 4*atan((ld)1); template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } namespace io { // TYPE ID (StackOverflow) template<class T> struct like_array : is_array<T>{}; template<class T, size_t N> struct like_array<array<T,N>> : true_type{}; template<class T> struct like_array<vector<T>> : true_type{}; template<class T> bool is_like_array(const T& a) { return like_array<T>::value; } // I/O void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } } // INPUT template<class T> void re(T& x) { cin >> x; } template<class Arg, class... Args> void re(Arg& first, Args&... rest); void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1,T2>& p); template<class T> void re(vector<T>& a); template<class T, size_t SZ> void re(array<T,SZ>& a); template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); } template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); } template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); } template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); } template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); } // OUTPUT template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& printArray(ostream& os, const T& a, int SZ) { os << '{'; F0R(i,SZ) { if (i) { os << ", "; if (is_like_array(a[i])) cout << "\n"; } os << a[i]; } os << '}'; return os; } template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) { return printArray(os,a,SZ); } template<class T> ostream& operator<<(ostream& os, const vector<T>& a) { return printArray(os,a,sz(a)); } template<class T> ostream& operator<<(ostream& os, const set<T>& a) { os << vector<T>(all(a)); return os; } template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) { os << vector<pair<T1,T2>>(all(a)); return os; } template<class T> void pr(const T& x) { cout << x << '\n'; } template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { cout << first << ' '; pr(rest...); } } using namespace io; namespace modOp { int ad(int a, int b, int mod = MOD) { return (a+b)%mod; } int sub(int a, int b, int mod = MOD) { return (a-b+mod)%mod; } int mul(int a, int b, int mod = MOD) { return (ll)a*b%mod; } int AD(int& a, int b, int mod = MOD) { return a = ad(a,b,mod); } int SUB(int& a, int b, int mod = MOD) { return a = sub(a,b,mod); } int MUL(int& a, int b, int mod = MOD) { return a = mul(a,b,mod); } int po (int b, int p, int mod = MOD) { return !p?1:mul(po(mul(b,b,mod),p/2,mod),p&1?b:1,mod); } int inv (int b, int mod = MOD) { return po(b,mod-2,mod); } int invGeneral(int a, int b) { // 0 < a < b, gcd(a,b) = 1 if (a == 0) return b == 1 ? 0 : -1; int x = invGeneral(b%a,a); return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b; } } using namespace modOp; int n,q; int CUM[7][1001], cum[7][7][1000][1000]; int in[3]; vi A; void init() { // you should actually read the stuff at the bottom setIO(); re(n); A.resz(n); re(A); re(q); F0R(i,q) { int l,r,x; re(l,r,x); l--, r--; F0R(a,7) if (x&(1<<a)) F0R(b,7) if (x&(1<<b)) { // pr(a,b,l,r); cum[a][b][l][r] ++; } F0R(a,7) if (x&(1<<a)) CUM[a][l] ++, CUM[a][r+1] --; } F0R(a,7) FOR(i,1,1001) CUM[a][i] += CUM[a][i-1]; F0R(a,7) F0R(b,7) FORd(len,1,n) F0R(i,n-len) { int t = cum[a][b][i][i+len]; cum[a][b][i][i+len-1] += t; cum[a][b][i+1][i+len] += t; if (len > 1) cum[a][b][i+1][i+len-1] -= t; } //pr(cum[1][1][0][0],cum[1][1][1][1]); in[0] = 1; FOR(i,1,3) in[i] = mul(in[i-1],(MOD+1)/2); } int main() { init(); // pr(CUM[1][0],cum[1][1][0][0]); int res = 0; F0R(i,n) FOR(j,i,n) { int cur = (i+1)*(n-j); if (i != j) cur *= 2; F0R(a,7) F0R(b,7) { int c1 = CUM[a][i], c2 = CUM[b][j], c3 = cum[a][b][i][j]; c1 -= c3, c2 -= c3; int b0 = (A[i]>>a)&1, b1 = (A[j]>>b)&1, CUR = cur<<(a+b); int ori = b0*b1; int t = (c1 > 0) + (c2 > 0) + (c3 > 0); if (t >= 2) MUL(CUR,in[2]); else if (c1) { if (b1 == 0) MUL(CUR,0); else MUL(CUR,in[1]); } else if (c2) { if (b0 == 0) MUL(CUR,0); else MUL(CUR,in[1]); } else if (c3) { MUL(CUR,mul(b0 == b1,in[1])); } else MUL(CUR,ori); // if (CUR) pr(a,b,i,j,cur,CUR); AD(res,CUR); } } MUL(res,po(2,q)); pr(res); // you should actually read the stuff at the bottom } /* stuff you should look for * int overflow, array bounds * special cases (n=1?), set tle * do smth instead of nothing and stay organized */

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp: In function 'void io::setIn(std::__cxx11::string)':
xorsum.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
xorsum.cpp: In function 'void io::setOut(std::__cxx11::string)':
xorsum.cpp:68:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...