oj.uz

Submission #502636

# Submission time Handle Problem Language Result Execution time Memory
502636 2022-01-06T11:13:51 Z stanislavpolyn Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2252 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for(int i = (a); i <= (b); ++i)
#define rf(i, a, b) for(int i = (a); i >= (b); --i)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template<typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
using ve = vector<T>;

const int N = 1e3 + 5;
const int MOD = 1e9 + 7;

int add(int a, int b) {
    a += b;
    if(a >= MOD) {
        return a - MOD;
    }
    return a;
}

int sub(int a, int b) {
    a -= b;
    if(a < 0) {
        return a + MOD;
    }
    return a;
}

int mult(int a, int b) {
    return 1LL * a * b % MOD;
}

int n, q;
int a[N], was[N];
int pref[N];
ve<array<int, 3>> Q;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n;

    fr(i, 1, n) {
        cin >> a[i];
        was[i] = a[i];
    }

    cin >> q;
    Q.resize(q);
    int res = 0;
    fr(i, 0, q - 1) {
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
    }

    fr(mask, 0, pw(q) - 1) {
        fr(i, 1, n) a[i] = was[i];
        fr(i, 0, q - 1) {
            if(mask & pw(i)) {
                fr(j, Q[i][0], Q[i][1]) a[j] ^= Q[i][2];
            }
        }
        int sum1 = 0;
        int sum2 = 0;
        fr(i, 1, n) {
            pref[i] = add(a[i], pref[i - 1]);

            res = add(res, mult(i, mult(pref[i], pref[i])));
            res = sub(res, mult(sum1, mult(2, pref[i])));
            res = add(res, sum2);

            sum1 = add(sum1, pref[i]);
            sum2 = add(sum2, mult(pref[i], pref[i]));
        }
    }

    cout << res << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 2252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 316 KB Output is correct
2 Correct 533 ms 316 KB Output is correct
3 Correct 478 ms 204 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 316 KB Output is correct
2 Correct 533 ms 316 KB Output is correct
3 Correct 478 ms 204 KB Output is correct
4 Incorrect 4 ms 328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 489 ms 316 KB Output is correct
10 Correct 533 ms 316 KB Output is correct
11 Correct 478 ms 204 KB Output is correct
12 Execution timed out 2080 ms 204 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 489 ms 316 KB Output is correct
10 Correct 533 ms 316 KB Output is correct
11 Correct 478 ms 204 KB Output is correct
12 Incorrect 4 ms 328 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Execution timed out 2078 ms 2252 KB Time limit exceeded
10 Halted 0 ms 0 KB -