oj.uz

Submission #685486

# Submission time Handle Problem Language Result Execution time Memory
685486 2023-01-24T12:34:10 Z opPO Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 4196 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 1e9 + 7;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e6 + 10;

struct Query
{
    int l;
    int r;
    int x;

    Query(int l, int r, int x) : l(l), r(r), x(x) {};
};

void add(int &x, int y)
{
    x += y;
    if (x >= mod) x %= mod;
}

void solve()
{
    int n;
    cin >> n;
    vec<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vec<Query> qs;
    int q;
    cin >> q;
    for (int t = 0; t < q; t++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        qs.pb(Query(l, r, x));
    }
    int ans = 0;
    for (int mask = 0; mask < (1 << q); mask++)
    {
        vec<int> xr(n + 2);
        for (int i = 0; i < q; i++)
        {
            if ((mask >> i) & 1)
            {
                xr[qs[i].l] ^= qs[i].x;
                xr[qs[i].r + 1] ^= qs[i].x;
            }
        }
        int p = 0;
        vec<int> b(n + 1);
        for (int i = 1; i <= n; i++)
        {
            p ^= xr[i];
            b[i] = a[i] ^ p;
        }
        for (int i = 1; i <= n; i++)
        {
            int s = 0;
            for (int j = i; j <= n; j++)
            {
                add(s, b[j]);
                add(ans, s * s);
            }
        }
    }
    cout << ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 11 ms 344 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 332 KB Output is correct
2 Correct 1206 ms 308 KB Output is correct
3 Correct 1202 ms 320 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 332 KB Output is correct
2 Correct 1206 ms 308 KB Output is correct
3 Correct 1202 ms 320 KB Output is correct
4 Incorrect 3 ms 596 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 11 ms 344 KB Output is correct
9 Correct 1209 ms 332 KB Output is correct
10 Correct 1206 ms 308 KB Output is correct
11 Correct 1202 ms 320 KB Output is correct
12 Incorrect 43 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 11 ms 344 KB Output is correct
9 Correct 1209 ms 332 KB Output is correct
10 Correct 1206 ms 308 KB Output is correct
11 Correct 1202 ms 320 KB Output is correct
12 Incorrect 3 ms 596 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Correct 11 ms 328 KB Output is correct
8 Correct 11 ms 344 KB Output is correct
9 Incorrect 19 ms 4196 KB Output isn't correct
10 Halted 0 ms 0 KB -