oj.uz

Submission #288382

# Submission time Handle Problem Language Result Execution time Memory
288382 2020-09-01T13:04:40 Z topovik XORanges (eJOI19_xoranges) C++17
0 / 100
 957 ms 12284 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define INF 1000000000

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e12;
const ll N = 1e6;

ll a[N];
ll val[N][2];
ll n,q;

void Build(ll l, ll r, ll posx, ll posy)
{
    if (l==r)
    {
        if (l*2+posy-2<n) val[posx][posy]=a[l*2+posy-2];
        return ;
    }
    ll mdl=(l+r)>>1;
    Build(l,mdl,posx*2,posy);
    Build(mdl+1,r,posx*2+1,posy);
    val[posx][posy]=val[posx*2][posy]^val[posx*2+1][posy];
}

void Upd(ll l, ll r, ll nom, ll zn,ll posx, ll posy)
{
    if (l>nom || r<nom) return ;
    if (l==r)           {val[posx][posy]=zn;return;}
    ll mdl=(l+r)>>1;
    Upd(l,mdl,nom,zn,posx*2,posy);
    Upd(mdl+1,r,nom,zn,posx*2+1,posy);
    val[posx][posy]=val[posx*2][posy]^val[posx*2+1][posy];
}

ll Sum(ll l, ll r, ll l1, ll r1, ll posx, ll posy)
{
    if (l1>r1) return 0;
    if (l1==l && r1==r) return val[posx][posy];
    ll mdl=(l+r)>>1;
    return Sum(l,mdl,l1,min(mdl,r1),posx*2,posy)+Sum(mdl+1,r,max(mdl+1,l1),r1,posx+2+1,posy);
}

int main()
{
    cin>>n>>q;
    for (ll i=0; i<n; i++) cin>>a[i];
    Build(1,(n+1)/2,1,0);
    Build(1,n/2,1,1);
    while (q>0)
    {
        q--;
        ll nom,x,y;
        cin>>nom>>x>>y;
        if (nom==1) Upd(1,(n+1)/2,(x+1)/2,y,1,(x+1)&1);
        else
        {
            if (!((y-x+1)&1)) cout<<0<<endl;
            else              cout<<Sum(1,(n+1)/2,(x+1)/2,(y+1)/2,1,(x+1)&1)<<endl;
        }
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 957 ms 12284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -