oj.uz

답안 #288409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288409 2020-09-01T13:23:57 Z topovik XORanges (eJOI19_xoranges) C++14
55 / 100
 1000 ms 9460 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 int N = 1e6;

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

void Build(int l, int r, int posx, int posy)
{
    if (l==r)
    {
        if ((l*2+posy-2)<n) val[posx][posy]=a[l*2+posy-2];
        return ;
    }
    int 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];
}

inline void Upd(int l, int r, int nom, int zn,int posx, int posy)
{
    if (l>nom || r<nom) return ;
    if (l==r)           {val[posx][posy]=zn;return;}
    int 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];
}

inline int Sum(int l, int r, int l1, int r1, int posx, int posy)
{
    if (l1>r1) return 0;
    if (l1==l && r1==r) return val[posx][posy];
    int 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 (int 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--;
        int 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
12.0 / 12.0

# 결과 실행 시간 메모리 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 #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 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
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 18 ms 384 KB Output is correct
12 Correct 18 ms 384 KB Output is correct
13 Correct 22 ms 384 KB Output is correct
14 Correct 22 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 987 ms 4436 KB Output is correct
2 Execution timed out 1052 ms 9460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 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
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 18 ms 384 KB Output is correct
12 Correct 18 ms 384 KB Output is correct
13 Correct 22 ms 384 KB Output is correct
14 Correct 22 ms 384 KB Output is correct
15 Correct 987 ms 4436 KB Output is correct
16 Execution timed out 1052 ms 9460 KB Time limit exceeded
17 Halted 0 ms 0 KB -