oj.uz

Submission #1027113

# Submission time Handle Problem Language Result Execution time Memory
1027113 2024-07-18T22:05:06 Z Dennis_Jason XORanges (eJOI19_xoranges) C++14
100 / 100
 411 ms 13500 KB 
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
//#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 5001
#define nl '\n'
#define INF 0x3f3f3f3
#define pii1 pair<int, pair<int,int>>  (1,(1,2));

#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
vector<int>v;
class segtree{
private:
    int n;
    vector<int>treeI;
    vector<int>treeP;
public:
    void init(int sz)
    {
        n=sz;
        treeI.resize(4*sz+1);
        treeP.resize(4*sz+1);
    }
    int calc(int a,int b)
    {
        return a^b;
    }
    void build(int node,int st,int dr,vector<int>&v)
    {
        if(st==dr)
        {
            if(st%2==1)
            {
                treeI[node]=v[st];
                treeP[node]=0;
            }
            else
            {
                treeI[node]=0;
                treeP[node]=v[st];
            }
            return;
        }
        int mid=(st+dr)/2;
        build(2*node,st,mid,v);
        build(2*node+1,mid+1,dr,v);
        treeI[node]=calc(treeI[2*node],treeI[2*node+1]);
        treeP[node]=calc(treeP[2*node],treeP[2*node+1]);
    }
    void update(int node,int st,int dr,int pos,int val)
    {
        if(st==dr)
        {
            if(st%2==1)
            {
                treeI[node]=val;
                treeP[node]=0;
            }
            else
            {
                treeI[node]=0;
                treeP[node]=val;
            }
            return;
        }
        int mid=(st+dr)/2;
        if(pos<=mid)
            update(2*node,st,mid,pos,val);
        else
            update(2*node+1,mid+1,dr,pos,val);
        treeI[node]=calc(treeI[2*node],treeI[2*node+1]);
        treeP[node]=calc(treeP[2*node],treeP[2*node+1]);
    }
    int query_I(int node,int st,int dr,int L,int R)
    {
        if(R<st|| dr<L)
            return 0;
        if(L<=st && dr<=R)
        {
            return treeI[node];
        }
        int mid=(st+dr)/2;
        int left=query_I(2*node,st,mid,L,R);
        int right=query_I(2*node+1,mid+1,dr,L,R);
        return left^right;

    }
    int query_P(int node,int st,int dr,int L,int R)
    {
        if(R<st|| dr<L)
            return 0;
        if(L<=st && dr<=R)
        {
            return treeP[node];
        }
        int mid=(st+dr)/2;
        int left=query_P(2*node,st,mid,L,R);
        int right=query_P(2*node+1,mid+1,dr,L,R);
        return left^right;

    }
    int query(int L,int R)
    {
        if(L%2==1)
            return query_I(1,1,n,L,R);
        else
            return query_P(1,1,n,L,R);
    }
    void build(vector<int>&v)
    {
        build(1,1,n,v);
    }
    void update(int pos,int val)
    {
        update(1,1,n,pos,val);
    }
    void check()
    {
        cout<<treeI[2]<<nl;
    }
};
/*
 *    1 2 3 4 5 6
 *    1 2 2 3 3 4 4 5 5 6
 *    v[l]^v[r]^query(l,r)/false
 *
 *    l,r
 *    1 4
 *    4 elemt de 1(r-l+1) = 1^2^3^4
 *    3 elem de 2(r-l) = 1^2^2^3^3^4=1^4 ,(x^x=0),(x^0=x)
 *    2 elem de3(r-l-1) = 1^2^3^2^3^4=1^2^2^3^3^4= 1^4
 *    1 elem de 4(r-l-2) =1^2^3^4
 *    ans=1^1^1^1^2^2^3^3^4^4^4^4=0
 *    if(r-l+1)%2==0 is 0?x
 *
 *    1 3
 *    3 elem de 1=1^2^3
 *    2 elem de 2=1^2^2^3=1^3
 *    1 elem de 3=1^2^3
 *    ans=1^1^1^2^2^3^3^3=1^3;
 *    1*3,2*2,3*3
 *
 *
 *      v
 *    3 2 3 4 5
 *    1 5
 *    5 elem de 1=3 ^ 2 ^ 3 ^ 4 ^ 5=3^2^4^5
 *    4 elem de 2=3^2 ^ 2^3 ^ 3^4 ^ 4^5=3^5
 *    3 elem de 3=3^2^3 ^ 2^3^4 ^ 3^4^5=5
 *    2 elem de 4= 3^2^3^4 ^ 2^3^4^5%=3^5
 *    1 elem de 5=3^2^3^4^5=2^4^5
 *    ans=2^2^3^3^5^5^5^5^5=5
      5 elemente:1*5,2*8,3*9,4*8,5*5
      3^3^5=5;
      6 elem
 *
 *        123456
 *       123   456
 *      12 3   45  6
 *     1 2    4 5
 *      if(ind%2==1) will count
 *      else no
 *
 */
segtree st;
signed main() {

    int n,q;
    cin>>n>>q;
    v.resize(n+1);
    st.init(n);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
    }
    st.build(v);

    for(int i=1;i<=q;++i)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int pos,val;
            cin>>pos>>val;
            st.update(pos,val);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            if((r-l+1)%2==0)
            {
                cout<<0<<nl;
            }
            else
            {
                cout<<st.query(l,r)<<nl;
            }

        }
    }


   return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 13488 KB Output is correct
2 Correct 370 ms 13444 KB Output is correct
3 Correct 378 ms 13500 KB Output is correct
4 Correct 343 ms 13140 KB Output is correct
5 Correct 395 ms 13140 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 11 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 9 ms 736 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 399 ms 13488 KB Output is correct
16 Correct 370 ms 13444 KB Output is correct
17 Correct 378 ms 13500 KB Output is correct
18 Correct 343 ms 13140 KB Output is correct
19 Correct 395 ms 13140 KB Output is correct
20 Correct 302 ms 13212 KB Output is correct
21 Correct 272 ms 13276 KB Output is correct
22 Correct 334 ms 13228 KB Output is correct
23 Correct 358 ms 12988 KB Output is correct
24 Correct 411 ms 13140 KB Output is correct