oj.uz

Submission #147766

# Submission time Handle Problem Language Result Execution time Memory
147766 2019-08-30T15:33:31 Z andrew Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 3448 KB 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
const ll mod = 1e9 + 7;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

struct qry{
    ll l, r, x;
};

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

    ll n;
    cin >> n;

    vector <ll> a(n + 1), b(n + 1), f(n + 2);

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

    ll q;
    cin >> q;

    vector <qry> c(q);

    for(int i = 0; i < q; i++){
        cin >> c[i].l >> c[i].r >> c[i].x;
    }

    ll ans = 0;

    for(int st = 0; st < pw(q); st++){
        for(int i = 1; i <= n; i++)f[i] = 0, b[i] = a[i];

        for(int i = 0; i < q; i++)if((st & pw(i))){
            f[c[i].l] ^= c[i].x;
            f[c[i].r + 1] ^= c[i].x;
        }

        ll delta = 0;

        for(int i = 1; i <= n; i++){
            delta ^= f[i];
            b[i] ^= delta;
        }

        ll pref = 0, scpref = 0, scpref2 = 0;

        for(int i = 1; i <= n; i++){
            pref += b[i];
            ans += i * sqr(pref);
            ans += scpref2;
            ans %= mod;
            ans -= (2 * scpref * pref) % mod;
            while(ans < 0)ans += mod;
            scpref += pref;
            scpref2 += sqr(pref);
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 3448 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 2015 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 384 KB Output is correct
2 Correct 378 ms 504 KB Output is correct
3 Correct 378 ms 504 KB Output is correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 380 ms 384 KB Output is correct
10 Correct 378 ms 504 KB Output is correct
11 Correct 378 ms 504 KB Output is correct
12 Execution timed out 2050 ms 376 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 380 ms 384 KB Output is correct
10 Correct 378 ms 504 KB Output is correct
11 Correct 378 ms 504 KB Output is correct
12 Incorrect 5 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Execution timed out 2024 ms 3448 KB Time limit exceeded
10 Halted 0 ms 0 KB -