oj.uz

Submission #651216

# Submission time Handle Problem Language Result Execution time Memory
651216 2022-10-18T03:05:13 Z Astrayt Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2772 KB 
//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define N 100005

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

void solve(){
    int n, ans = 0, mod = 1e9 + 7; cin >> n;
    vector<int> v(n);
    for(auto &x:v) {
        cin >> x;
    }
    int q; cin >> q;
    vector<qry> Q(q);
    for(auto &qq:Q){
        cin >> qq.l >> qq.r >> qq.x;
        qq.l--; qq.r--;
    }
    for(int s = 0; s < (1<<q); ++s){
        vector<int> tmp = v;
        for(int i = 0; i < q; ++i){
            auto qq = Q[i];
            if(s & (1 << i)){
                for(int j = qq.l; j <= qq.r; ++j){
                    tmp[j] ^= qq.x;
                }
            }
        }
        vector<int> p(1, 0), p2, p3;
        for(int i = 0; i < n; ++i){
            p.pb(tmp[i] + p[i]);
            p.back() %= mod;
        }
        p2 = p3 = p;
        for(int i = 1; i <= n; ++i){
            p2[i] = p2[i] + p2[i - 1];
            p3[i] = p3[i] * p3[i];
            p3[i] %= mod, p2[i] %= mod;
            p3[i] = p3[i - 1] + p3[i];
            p3[i] %= mod;
        }
        for(int i = 1; i <= n; ++i){
            ans = (ans + i * p[i] % mod * p[i]) % mod;
            ans = (ans - 2 * p[i] % mod * p2[i - 1] % mod) % mod;
            ans = (ans + p3[i - 1]) % mod;
        }
    }
    cout << (ans + mod) % mod;
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 4 ms 212 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2772 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 2071 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 1276 ms 300 KB Output is correct
2 Correct 1232 ms 308 KB Output is correct
3 Correct 1245 ms 300 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 300 KB Output is correct
2 Correct 1232 ms 308 KB Output is correct
3 Correct 1245 ms 300 KB Output is correct
4 Incorrect 6 ms 340 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 4 ms 212 KB Output is correct
9 Correct 1276 ms 300 KB Output is correct
10 Correct 1232 ms 308 KB Output is correct
11 Correct 1245 ms 300 KB Output is correct
12 Incorrect 25 ms 332 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 4 ms 212 KB Output is correct
9 Correct 1276 ms 300 KB Output is correct
10 Correct 1232 ms 308 KB Output is correct
11 Correct 1245 ms 300 KB Output is correct
12 Incorrect 6 ms 340 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 4 ms 212 KB Output is correct
9 Incorrect 18 ms 2772 KB Output isn't correct
10 Halted 0 ms 0 KB -