oj.uz

Submission #272131

# Submission time Handle Problem Language Result Execution time Memory
272131 2020-08-18T09:40:45 Z JuliusMieliauskas XORanges (eJOI19_xoranges) C++14
75 / 100
 1000 ms 8748 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vll vector<long long>
#define MOD 1000000007
#define endl '\n'

typedef long long ll;

void print(vi v){
    cout<<"Contents of vector:\n";
    for(auto x : v) cout<<x<<" ";
    cout<<endl<<endl;
}

void solve(){
    int n, q; cin>>n>>q;
    int ar[n], prefeven[n+1] = {0}, prefodd[n+1] = {0};
    for(int i = 0; i<n; i++) cin>>ar[i];

    prefodd[0] = 0;
    prefeven[0] = 0;
    prefodd[1] = ar[0];
    prefeven[2] = ar[1];

    for(int i = 4; i<=n; i+=2) {
        prefeven[i] = prefeven[i-2] ^ ar[i-1];
    }

    for(int i = 3; i<=n; i+=2) {
        prefodd[i] = prefodd[i-2] ^ ar[i-1];
        //cout<<i<<" is equal to "<<prefodd[i-2]<<" xor "<<ar[i-1]<<endl;
    }

    /*cout<<"Prefsodd: "<<endl;
    for(int i = 0; i<=n; i++) cout<<prefodd[i]<<" ";
    cout<<endl<<endl;

    cout<<"Prefseven: "<<endl;
    for(int i = 0; i<=n; i++) cout<<prefeven[i]<<" ";
    cout<<endl<<endl;*/

    for(int i = 0; i<q; i++){
        int type; cin>>type;
        if(type == 1){
            int ind, value; cin>>ind>>value;

            ar[ind-1] = value;

            /*cout<<"array: "<<endl;
            for(int i = 0; i<=n; i++) cout<<ar[i]<<" ";
            cout<<endl<<endl;*/

            prefodd[0] = 0;
            prefeven[0] = 0;
            prefodd[1] = ar[0];
            prefeven[2] = ar[1];

            for(int i = 4; i<=n; i+=2) {
                prefeven[i] = prefeven[i-2] ^ ar[i-1];
            }

            for(int i = 3; i<=n; i+=2) {
                prefodd[i] = prefodd[i-2] ^ ar[i-1];
                //cout<<i<<" is equal to "<<prefodd[i]<<" of "<<prefodd[i-2]<<" xor "<<ar
            }

            /*cout<<"Prefsodd: "<<endl;
            for(int i = 0; i<=n; i++) cout<<prefodd[i]<<" ";
            cout<<endl<<endl;*/

        } else {
            int from, to; cin>>from>>to;

            if((to-from+1)%2 == 0){
                cout<<"0"<<endl;
                continue;
            }

            int ans = 0;

            if(from%2) {
                 if(from != 1) ans = prefodd[to] ^ prefodd[from-2];
                 else ans = prefodd[to] ^ 0;
                 //cout<<"odd"<<endl;
            } else {
                ans = prefeven[to] ^ prefeven[from-2];
            }

            /*cout<<"Map: "<<endl;
            for(auto x : m){
                cout<<x.first<<" : "<<x.second<<endl;
            }*/

            cout<<ans<<endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    //ifstream cin("input.txt"); ofstream cout("output.txt");///cia failai

    //int T; cin>>T;
    int T = 1;

    for(int it = 1; it<=T; it++){
        solve();

    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 41 ms 384 KB Output is correct
12 Correct 40 ms 384 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 5240 KB Output is correct
2 Correct 100 ms 8696 KB Output is correct
3 Correct 118 ms 8748 KB Output is correct
4 Correct 92 ms 8440 KB Output is correct
5 Correct 95 ms 8440 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 41 ms 384 KB Output is correct
12 Correct 40 ms 384 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 104 ms 5240 KB Output is correct
16 Correct 100 ms 8696 KB Output is correct
17 Correct 118 ms 8748 KB Output is correct
18 Correct 92 ms 8440 KB Output is correct
19 Correct 95 ms 8440 KB Output is correct
20 Execution timed out 1090 ms 4988 KB Time limit exceeded
21 Halted 0 ms 0 KB -