oj.uz

Submission #142963

# Submission time Handle Problem Language Result Execution time Memory
142963 2019-08-12T12:14:09 Z Benq Intergalactic ship (IZhO19_xorsum) C++14
100 / 100
 556 ms 192316 KB 
#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
*/

Compilation message

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); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 19 ms 19832 KB Output is correct
7 Correct 19 ms 19704 KB Output is correct
8 Correct 21 ms 19768 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 19728 KB Output is correct
2 Correct 26 ms 19720 KB Output is correct
3 Correct 19 ms 19792 KB Output is correct
4 Correct 20 ms 19832 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 192228 KB Output is correct
2 Correct 540 ms 192220 KB Output is correct
3 Correct 492 ms 192252 KB Output is correct
4 Correct 462 ms 192300 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 7 ms 6392 KB Output is correct
3 Correct 14 ms 6392 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 7 ms 6392 KB Output is correct
3 Correct 14 ms 6392 KB Output is correct
4 Correct 8 ms 6264 KB Output is correct
5 Correct 8 ms 6264 KB Output is correct
6 Correct 8 ms 6392 KB Output is correct
7 Correct 8 ms 6264 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 19 ms 19832 KB Output is correct
7 Correct 19 ms 19704 KB Output is correct
8 Correct 21 ms 19768 KB Output is correct
9 Correct 8 ms 6264 KB Output is correct
10 Correct 7 ms 6392 KB Output is correct
11 Correct 14 ms 6392 KB Output is correct
12 Correct 20 ms 19704 KB Output is correct
13 Correct 20 ms 19752 KB Output is correct
14 Correct 20 ms 19832 KB Output is correct
15 Correct 20 ms 19832 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 19 ms 19832 KB Output is correct
7 Correct 19 ms 19704 KB Output is correct
8 Correct 21 ms 19768 KB Output is correct
9 Correct 8 ms 6264 KB Output is correct
10 Correct 7 ms 6392 KB Output is correct
11 Correct 14 ms 6392 KB Output is correct
12 Correct 8 ms 6264 KB Output is correct
13 Correct 8 ms 6264 KB Output is correct
14 Correct 8 ms 6392 KB Output is correct
15 Correct 8 ms 6264 KB Output is correct
16 Correct 20 ms 19704 KB Output is correct
17 Correct 20 ms 19752 KB Output is correct
18 Correct 20 ms 19832 KB Output is correct
19 Correct 20 ms 19832 KB Output is correct
20 Correct 228 ms 96712 KB Output is correct
21 Correct 203 ms 96532 KB Output is correct
22 Correct 187 ms 96632 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 19 ms 19832 KB Output is correct
7 Correct 19 ms 19704 KB Output is correct
8 Correct 21 ms 19768 KB Output is correct
9 Correct 49 ms 19728 KB Output is correct
10 Correct 26 ms 19720 KB Output is correct
11 Correct 19 ms 19792 KB Output is correct
12 Correct 20 ms 19832 KB Output is correct
13 Correct 556 ms 192228 KB Output is correct
14 Correct 540 ms 192220 KB Output is correct
15 Correct 492 ms 192252 KB Output is correct
16 Correct 462 ms 192300 KB Output is correct
17 Correct 8 ms 6264 KB Output is correct
18 Correct 7 ms 6392 KB Output is correct
19 Correct 14 ms 6392 KB Output is correct
20 Correct 8 ms 6264 KB Output is correct
21 Correct 8 ms 6264 KB Output is correct
22 Correct 8 ms 6392 KB Output is correct
23 Correct 8 ms 6264 KB Output is correct
24 Correct 20 ms 19704 KB Output is correct
25 Correct 20 ms 19752 KB Output is correct
26 Correct 20 ms 19832 KB Output is correct
27 Correct 20 ms 19832 KB Output is correct
28 Correct 228 ms 96712 KB Output is correct
29 Correct 203 ms 96532 KB Output is correct
30 Correct 187 ms 96632 KB Output is correct
31 Correct 548 ms 192200 KB Output is correct
32 Correct 527 ms 192180 KB Output is correct
33 Correct 503 ms 192316 KB Output is correct
34 Correct 462 ms 192248 KB Output is correct
35 Correct 453 ms 192228 KB Output is correct
36 Correct 456 ms 192180 KB Output is correct