Submission #1103172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103172		Zero_OP	Intergalactic ship (IZhO19_xorsum)	C++14	45 / 100	835 ms	12352 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

const int MAX = 1e3 + 5;
const int mod = 1e9 + 7;

struct mint{
    int v;
    mint(int v = 0) : v(v) {}
    mint(ll v = 0) : v(v % mod) {}
    mint() = default;

    mint& operator += (const mint& a){ v += a.v; if(v >= mod) v -= mod; return *this; }
    mint& operator -= (const mint& a){ if(v < 0) v += mod; return *this; }
    mint& operator *= (const mint& a){ v = 1LL * v * a.v % mod; return *this; }
    mint& operator /= (const mint& a){ return (*this) *= a.inv(); }

    mint power(ll pw) const {
        mint res(1);
        mint base = *this;
        for(; pw > 0; pw /= 2, base *= base){
            if(pw & 1) res *= base;
        }
        return res;
    }

    mint inv() const {
        return power(mod - 2);
    }

    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
    friend mint operator / (mint a, const mint& b){ return a /= b; }

    friend istream& operator >> (istream& in, mint& x){ return in >> x.v; }
    friend ostream& operator << (ostream& out, const mint& x){ return out << x.v; }

    #define define_logical_operation(o) friend bool operator o (const mint& a, const mint& b){ return a.v o b.v; }
    define_logical_operation(==)
    define_logical_operation(!=)
    define_logical_operation(<)
    define_logical_operation(>)
    define_logical_operation(<=)
    define_logical_operation(>=)
};

int n, q, a[MAX], L[MAX], R[MAX], x[MAX];

namespace last_subtask{
    vector<vector<int>> A, B, C;
    vector<mint> pw2;

    void updateRect(vector<vector<int>>& a, int x1, int y1, int x2, int y2){
        if(x1 <= x2 && y1 <= y2){
            a[x1][y1] += 1;
            if(x2 < n) a[x2 + 1][y1] -= 1;
            if(y2 < n) a[x1][y2 + 1] -= 1;
            if(x2 < n && y2 < n) a[x2 + 1][y2 + 1] += 1;
        }
    }

    mint contribution_of_pair(int u, int v){
        mint sum(0);
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j){
            A[i][j] = B[i][j] = C[i][j] = 0;
        }

        for(int i = 1; i <= q; ++i){
            bool ia = (x[i] >> u & 1);
            bool jb = (x[i] >> v & 1);
            if(ia && jb){
                updateRect(A, L[i], L[i], R[i], R[i]);
                updateRect(B, L[i], R[i] + 1, R[i], n);
                updateRect(C, 1, L[i], L[i] - 1, R[i]);
            } else if(ia){
                updateRect(B, L[i], 1, R[i], n);
            } else if(jb){
                updateRect(C, 1, L[i], n, R[i]);
            }
        }

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
                B[i][j] += B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1];
                C[i][j] += C[i - 1][j] + C[i][j - 1] - C[i - 1][j - 1];
            }
        }

        for(int i = 1; i <= n; ++i){
            bool on_i = (a[i] >> u & 1);
            for(int j = i; j <= n; ++j){
                bool on_j = (a[j] >> v & 1);

                int a = A[i][j];
                int b = B[i][j];
                int c = C[i][j];
                int d = q - a - b - c;

                auto calculate = [&](int n, bool bit) -> mint{
                    if(n == 0) return mint(bit ? 0 : 1);
                    return pw2[n - 1];
                };

                mint ways(0);
                for(int ta = 0; ta < 2; ++ta){
                    for(int tb = 0; tb < 2; ++tb){
                        for(int tc = 0; tc < 2; ++tc){
                            if(((on_i + ta + tb) & 1) && ((on_j + ta + tc) & 1)){
                                mint cur = calculate(a, ta) * calculate(b, tb) * calculate(c, tc);
                                ways += cur;
                            }
                        }
                    }
                }

                ways *= pw2[d];
                mint num_ranges = mint(i) * mint(n - j + 1);
                mint e = mint(i == j ? 1 : 2);
                mint ret = num_ranges * ways * e * pw2[u + v];
                sum += ret;
            }
        }

        return sum;
    }

    void solve(){
        mint ans(0);

        A = vector<vector<int>>(n + 1, vector<int>(n + 1));
        B = vector<vector<int>>(n + 1, vector<int>(n + 1));
        C = vector<vector<int>>(n + 1, vector<int>(n + 1));

        pw2.resize(max(16, q + 1), mint(0));
        pw2[0] = mint(1);
        for(int i = 1; i <= max(15, q); ++i){
            pw2[i] = pw2[i - 1] + pw2[i - 1];
        }


        for(int a = 0; a < 7; ++a){
            for(int b = 0; b < 7; ++b){
                ans += contribution_of_pair(a, b);
            }
        }

        cout << ans << '\n';
    }
}

void testcase(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> L[i] >> R[i] >> x[i];
    }

    last_subtask::solve();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'bool minimize(T&, const T&)':
xorsum.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
xorsum.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
xorsum.cpp: In function 'bool maximize(T&, const T&)':
xorsum.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
xorsum.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:199:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 19 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8