제출 #497197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497197		Karabasan	XORanges (eJOI19_xoranges)	C++17	100 / 100	120 ms	9036 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse4,avx")
#pragma GCC optimize("unroll-loops")
#define fast1 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
int n,q;
int tek[100005];
int cift[100005];
int seg1[400005];
int seg2[400005];
int u;
int y;
void build(int x,int bas,int son)
{
    if(bas==son)
    {
        seg1[x]=tek[bas];
        return;
    }
    int orta=(bas+son)/2;
    build(2*x,bas,orta);
    build(2*x+1,orta+1,son);
    seg1[x]=seg1[2*x]^seg1[2*x+1];
}
void build2(int x,int bas,int son)
{
    if(bas==son)
    {
        seg2[x]=cift[bas];
        return;
    }
    int orta=(bas+son)/2;
    build2(2*x,bas,orta);
    build2(2*x+1,orta+1,son);
    seg2[x]=seg2[2*x]^seg2[2*x+1];
}
void update(int x,int bas,int son,int ind,int val)
{
    if(bas==son)
    {
        seg1[x]=val;
        return;
    }
    int orta=(bas+son)/2;
    if(ind<=orta)
        update(2*x,bas,orta,ind,val);
    else
        update(2*x+1,orta+1,son,ind,val);
    seg1[x]=seg1[2*x]^seg1[2*x+1];
}
void update2(int x,int bas,int son,int ind,int val)
{
    if(bas==son)
    {
        seg2[x]=val;
        return;
    }
    int orta=(bas+son)/2;
    if(ind<=orta)
        update2(2*x,bas,orta,ind,val);
    else
        update2(2*x+1,orta+1,son,ind,val);
    seg2[x]=seg2[2*x]^seg2[2*x+1];
}
int query(int x,int bas,int son,int l,int r)
{
    if(bas>r||son<l)
        return 0;
    if(bas>=l&&son<=r)
        return seg1[x];
    int orta=(bas+son)/2;
    return query(2*x,bas,orta,l,r)^query(2*x+1,orta+1,son,l,r);
}
int query2(int x,int bas,int son,int l,int r)
{
    if(bas>r||son<l)
        return 0;
    if(bas>=l&&son<=r)
        return seg2[x];
    int orta=(bas+son)/2;
    return query2(2*x,bas,orta,l,r)^query2(2*x+1,orta+1,son,l,r);
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
            cin>>tek[++u];
        else cin>>cift[++y];
    }
    build(1,1,u);
    build2(1,1,y);
    while(q--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==1)
        {
            if(b%2==1)
                update(1,1,u,(b+1)/2,c);
            else update2(1,1,y,b/2,c);
        }
        else
        {
            if((c-b)%2==1)
                cout<<0<<endl;
            else
            {
                if(b%2==1)
                    cout<<query(1,1,u,(b+1)/2,(b+1)/2+(c-b)/2)<<endl;
                else
                    cout<<query2(1,1,y,b/2,b/2+(c-b)/2)<<endl;
            }
        }
    }
}
signed main()
{
    fast1;
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25