oj.uz

Submission #286231

# Submission time Handle Problem Language Result Execution time Memory
286231 2020-08-30T08:35:41 Z lukameladze XORanges (eJOI19_xoranges) C++14
100 / 100
 676 ms 16120 KB 
# include <bits/stdc++.h>
using namespace std;
long long n,q,a[300005],ty,w,idx,val,tree[5][1200005],ans,x,ri,le;
void update(int node, int le, int ri, int idx, int val, int w)
{
       if (le>idx || ri<idx) return;
     if (idx==le && idx==ri)
     {
          tree[w][node]^=val;
          return ;
     }
     long long mid=(le+ri)/2;
     update(2*node, le, mid, idx, val , w);
     update(2*node+1, mid+1, ri , idx, val, w);
     tree[w][node]=tree[w][2*node]^tree[w][2*node+1];
}
long long getans(int node, int le, int ri, int start, int end, int w)
{
	if (le>end || ri<start) return 0;
	if (le>=start && ri<=end) 
	{
		return tree[w][node];
	}
	long long mid=(le+ri)/2;
	long long p1=getans(2*node, le, mid, start, end,w);
	 long long p2=getans(2*node+1, mid+1, ri, start, end,w);
	return p1^p2;
}
int main()
{
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n>>q;
     for (int i=1; i<=n; i++)
     {
          cin>>a[i];
          if (i%2==1)
          {
               update(1,1,n,i,a[i],1);
          }
          else
          {
               update(1,1,n, i,a[i],0);
          }
     }
     //cout<<1<<endl;
     for (int i=1; i<=q; i++)
     {
          cin>>ty;
          if (ty==1)
          {
               cin>>idx>>val;
               w=val^a[idx];
               update(1,1,n, idx, w, idx%2);
               a[idx]=val;
          }
          else
          {
               cin>>le>>ri;
               x=(ri-le+1);
               if (x%2==0)
               {
                    cout<<0<<endl;
                    continue;
               }//cout<<le<<" "<<ri<<"   ";
                    cout<<getans(1,1,n,le,ri,le%2)<<endl;
          }
          
     }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory 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

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory 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 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 10 ms 640 KB Output is correct
12 Correct 10 ms 640 KB Output is correct
13 Correct 14 ms 640 KB Output is correct
14 Correct 17 ms 640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 11384 KB Output is correct
2 Correct 676 ms 16120 KB Output is correct
3 Correct 667 ms 16120 KB Output is correct
4 Correct 626 ms 15868 KB Output is correct
5 Correct 627 ms 15864 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory 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 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 10 ms 640 KB Output is correct
12 Correct 10 ms 640 KB Output is correct
13 Correct 14 ms 640 KB Output is correct
14 Correct 17 ms 640 KB Output is correct
15 Correct 663 ms 11384 KB Output is correct
16 Correct 676 ms 16120 KB Output is correct
17 Correct 667 ms 16120 KB Output is correct
18 Correct 626 ms 15868 KB Output is correct
19 Correct 627 ms 15864 KB Output is correct
20 Correct 460 ms 16084 KB Output is correct
21 Correct 463 ms 15864 KB Output is correct
22 Correct 467 ms 15992 KB Output is correct
23 Correct 618 ms 15992 KB Output is correct
24 Correct 607 ms 15864 KB Output is correct