oj.uz

Submission #1103174

# Submission time Handle Problem Language Result Execution time Memory
1103174 2024-10-20T12:47:32 Z Zero_OP Intergalactic ship (IZhO19_xorsum) C++14
100 / 100
 983 ms 14932 KB 
#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 = 1e5 + 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

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.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 8 ms 592 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 8 ms 592 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2640 KB Output is correct
2 Correct 14 ms 852 KB Output is correct
3 Correct 9 ms 596 KB Output is correct
4 Correct 8 ms 612 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 12344 KB Output is correct
2 Correct 821 ms 12572 KB Output is correct
3 Correct 803 ms 12344 KB Output is correct
4 Correct 802 ms 12112 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 608 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 8 ms 592 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 10 ms 592 KB Output is correct
13 Correct 9 ms 592 KB Output is correct
14 Correct 11 ms 592 KB Output is correct
15 Correct 10 ms 616 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 8 ms 592 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 4 ms 608 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 10 ms 592 KB Output is correct
17 Correct 9 ms 592 KB Output is correct
18 Correct 11 ms 592 KB Output is correct
19 Correct 10 ms 616 KB Output is correct
20 Correct 300 ms 5984 KB Output is correct
21 Correct 259 ms 5964 KB Output is correct
22 Correct 242 ms 5972 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 8 ms 592 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Correct 63 ms 2640 KB Output is correct
10 Correct 14 ms 852 KB Output is correct
11 Correct 9 ms 596 KB Output is correct
12 Correct 8 ms 612 KB Output is correct
13 Correct 807 ms 12344 KB Output is correct
14 Correct 821 ms 12572 KB Output is correct
15 Correct 803 ms 12344 KB Output is correct
16 Correct 802 ms 12112 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 4 ms 504 KB Output is correct
21 Correct 4 ms 608 KB Output is correct
22 Correct 4 ms 596 KB Output is correct
23 Correct 4 ms 596 KB Output is correct
24 Correct 10 ms 592 KB Output is correct
25 Correct 9 ms 592 KB Output is correct
26 Correct 11 ms 592 KB Output is correct
27 Correct 10 ms 616 KB Output is correct
28 Correct 300 ms 5984 KB Output is correct
29 Correct 259 ms 5964 KB Output is correct
30 Correct 242 ms 5972 KB Output is correct
31 Correct 950 ms 14932 KB Output is correct
32 Correct 879 ms 14924 KB Output is correct
33 Correct 983 ms 14676 KB Output is correct
34 Correct 942 ms 14676 KB Output is correct
35 Correct 921 ms 14676 KB Output is correct
36 Correct 895 ms 14676 KB Output is correct