oj.uz

Submission #775435

# Submission time Handle Problem Language Result Execution time Memory
775435 2023-07-06T11:38:41 Z SalihSahin XORanges (eJOI19_xoranges) C++14
55 / 100
 1000 ms 11124 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fastio cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0)
using namespace std;

const int N = 5e3 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9*2;


struct SegT{
  vector<int> tree;

  void init(int n){
    tree.resize(n*4);
  }

  void build(vector<int> a, int v, int tl, int tr){
    if(tl == tr) tree[v] = a[tl];
    else{
        int tm = (tl + tr)/2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] ^ tree[v*2+1];
    }
  }

  int query(int v, int tl, int tr, int l, int r){
    if(l > r) return 0;
    if(l == tl && r == tr) return tree[v];
    int tm = (tl + tr)/2;
    return query(v*2, tl, tm, l, min(tm, r)) ^ query(v*2+1, tm+1, tr, max(l, tm+1), r);
  }

  void update(int v, int tl, int tr, int pos, int val){
    if(tl == tr) tree[v] = val;
    else{
        int tm = (tl + tr)/2;

        if(pos <= tm){
            update(v*2, tl, tm, pos, val);
        }
        else update(v*2+1, tm+1, tr, pos, val);

        tree[v] = tree[v*2] ^ tree[v*2+1];
    }
  }
};

int main(){
  fastio;
  SegT segeven, segodd;
  int n, q;
  cin>>n>>q;
  vector<int> a(n);
  vector<int> odd, even;
  for(int i = 0; i < n; i++){
    cin>>a[i];
    if(i%2) odd.pb(a[i]);
    else even.pb(a[i]);
  }
  segeven.init(even.size());
  segeven.build(even, 1, 0, even.size()-1);

  segodd.init(odd.size());
  segodd.build(odd, 1, 0, odd.size()-1);

  while(q--){
    int x;
    cin>>x;
    if(x == 1){
        int i, nv;
        cin>>i>>nv;
        i--;

        if(i%2) segodd.update(1, 0, odd.size()-1, i/2, nv);
        else segeven.update(1, 0, even.size()-1, i/2, nv);
    }
    else{
        int l, u;
        cin>>l>>u;
        l--, u--;

        if((u-l+1)%2){
            int ql = l/2, qu = u/2;
            if(l&1) cout<<segodd.query(1, 0, odd.size()-1, ql, qu)<<endl;
            else cout<<segeven.query(1, 0, even.size()-1, ql, qu)<<endl;
        }
        else cout<<0<<endl;
    }
  }

  return 0;
}

Subtask #1
12.0 / 12.0

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

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 8 ms 596 KB Output is correct
14 Correct 8 ms 596 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 8 ms 596 KB Output is correct
14 Correct 8 ms 596 KB Output is correct
15 Execution timed out 1083 ms 11124 KB Time limit exceeded
16 Halted 0 ms 0 KB -