CSES - Aalto Competitive Programming 2024 - wk4 - Mon - Results
Submission details
Task:Xor sum
Sender:minghao
Submission time:2024-09-23 16:22:39 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.32 sdetails

Compiler report

input/code.cpp: In function 'void Test()':
input/code.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen("temp\\in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
input/code.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
input/code.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~...

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N=10005, INF=0x3f3f3f3f;
/*----------------------------------------------------------------------------*/
template<typename Value, typename Tag>
struct Node
{
int id, l, r;
Value val;
Tag tag;
inline int length()const
{
return r-l+1;
}
inline bool disjoint(const int& l_bor, const int& r_bor)const
{
return l_bor>r || r_bor<l;
}// (l, r<l_bor)/(r_bor>l, r)
inline bool subset(const int& l_bor, const int& r_bor)const
{
return l_bor<=l && r_bor>=r;
}// [l_bor, l, r, r_bor]
};
template<typename Value, typename Tag>
class SegmentTree
{
public:
typedef Value (*FucMer)(Value, Value);
typedef void (*FucCov)(Node<Value, Tag>*, Tag);
SegmentTree(const FucMer f1, const FucCov f2, Value val, Tag tag)
: Merge(f1), Cover(f2), val_zero_(val), tag_zero_(tag) {}
void Init(const int& size, const vector<Value>& v)
{
l_range_=1, r_range_=size;
nodes_.resize(size<<2);
Build(1, l_range_, r_range_, v);
}
inline Node<Value, Tag>* identify(const int& p)
{
return &nodes_[p];
}
inline Node<Value, Tag>* l_child(const Node<Value, Tag>* p)
{
return &nodes_[p->id<<1];
}// 2*id for the left child
inline Node<Value, Tag>* r_child(const Node<Value, Tag>* p)
{
return &nodes_[p->id<<1|1];
}// 2*id+1 for the right child
void Modify(const int& pos, const Tag& tag)
{
Modify(identify(1), pos, pos, tag);
}// point change
void Modify(const int& l_bor, const int& r_bor, const Tag& tag)
{
Modify(identify(1), l_bor, r_bor, tag);
}// section change
Value Query(const int& pos)
{
return Query(identify(1), pos, pos);
}// point query
Value Query(const int& l_bor, const int& r_bor)
{
return Query(identify(1), l_bor, r_bor);
}// section query
private:
const FucMer Merge;
const FucCov Cover;
const Value val_zero_;
const Tag tag_zero_;
int l_range_, r_range_;
vector<Node<Value, Tag>> nodes_;
inline void PushUp(Node<Value, Tag>* p)
{
p->val=Merge(l_child(p)->val, r_child(p)->val);
}
inline void PushDown(Node<Value, Tag>* p)
{
Cover(l_child(p), p->tag);
Cover(r_child(p), p->tag);
p->tag=tag_zero_;
}
void Build(int cur, int l_cur, int r_cur, const vector<Value>& v)
{
Node<Value, Tag> *p=identify(cur);
p->id=cur, p->l=l_cur, p->r=r_cur;
p->tag=tag_zero_;
if(l_cur>r_cur) return;
if(l_cur==r_cur) { p->val=v[l_cur]; return; }
int mid=(l_cur+r_cur)>>1;
Build(cur<<1, l_cur, mid, v);
Build(cur<<1|1, mid+1, r_cur, v);
PushUp(p);
}
void Modify(Node<Value, Tag> *p, const int& l_bor, const int& r_bor,
const Tag& tag)
{
if(p->disjoint(l_bor, r_bor)) return;
if(p->subset(l_bor, r_bor)) { Cover(p, tag); return; }
if(p->tag!=tag_zero_) PushDown(p);
Modify(l_child(p), l_bor, r_bor, tag);
Modify(r_child(p), l_bor, r_bor, tag);
PushUp(p);
}
Value Query(Node<Value, Tag>* p, const int& l_bor, const int& r_bor)
{
if(p->disjoint(l_bor, r_bor)) return val_zero_;
if(p->subset(l_bor, r_bor)) return p->val;
if(p->tag!=tag_zero_) PushDown(p);
return Merge(Query(l_child(p), l_bor, r_bor),
Query(r_child(p), l_bor, r_bor));
}
};
/*----------------------------------------------------------------------------*/
auto h1=[](int a, int b) -> int { return a ^ b; };
auto h2=[](Node<int, int>* p, int x) { p->val=x; };
SegmentTree<int, int> h_xor(h1, h2, 0, 0);
void Test()
{
freopen("temp\\in.txt", "r", stdin);
}
int main()
{
// Test();
int n, q;
scanf("%d%d", &n, &q);
vector<int> v;
v.push_back(0);
for(int i=1, x; i<=n; i++)
{
scanf("%d", &x);
v.push_back(x);
}
h_xor.Init(n, v);
while(q--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", h_xor.Query(a, b));
}
return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
8 36
7 6 4 6 2 9 4 8
1 1
1 2
1 3
...

correct output
7
1
5
3
1
...

user output
7
1
5
3
1
...

Test 2

Verdict: ACCEPTED

input
200000 200000
921726510 307633388 992247073 ...

correct output
834756431
130379787
403037296
308618218
784778243
...

user output
834756431
130379787
403037296
308618218
784778243
...
Truncated