Submission #581082

#	Time	Username	Problem	Language	Result	Execution time	Memory
581082		TimDee	XORanges (eJOI19_xoranges)	C++14	100 / 100	154 ms	24648 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

#define paiu return
#define moment 0;
 
#define int long long
#define ll long long
 
#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)
#define forrr(i,j,x) for (int i=j; i<x; i++)
 
#define di(a,n) deque<int> a(n,0)
#define dll(a,n) deque<ll> a(n,0)
#define vi(a,n) vector<int> a(n,0)
#define vll(a,n) vector<ll> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

vector<int> tow(1e6+5);
vector<int> dp(1e6+5);
void ini() {
    tow[0]=0;
    int sum=0;
    for (int i=1; i<=1e6; i++) {
        tow[i]=sum+1;
        sum+=tow[i];
    }

    dp[0]=0;
    for (int i=1; i<=1e6; i++) {



    }
}

int pw2(int x, vector<int>&a) {
    int ret=1;
    for (int bit=32; bit>=0; bit--) {
        if (x&(1ll<<bit)) { ret*=a[bit]; ret%=mod; }
    }
    return ret;
}

struct segtree {
    
    vector<int> tree;
    int size;
    int n;
    int neutral;
    
    void put(int i, int v) {
        
        tree[i]=v;
        
    }
    
    int combine(int i, int j) {
        //for min
        //return min(i,j);
        //for max
        //return max(i,j);
        //for sum
        //return i+j;
        return i^j;
    }
 
    void update(int x, int l, int r, int i) {
        
        if (i>=r || i<l) return;
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid,i);
        update(2*x+2,mid,r,i);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    void update(int x, int l, int r) {
 
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid);
        update(2*x+2,mid,r);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    segtree(vector<int>&a, int neutr) {
        
        n=a.size();
       
        //for min
        //neutral = inf;
        //for max
        //neutral = -inf;
        //for sum
        neutral = neutr;

        size=1;
        while (size < n) size*=2;
        
        tree.assign(2*size-1,neutral);
        
        forr(i,n) put(size-1+i,a[i]);
        
        update(0,0,size);
        
    }
    
    void clear() {
        
        tree.assign(2*size-1,0);
        
    }
    
    int calc(int x, int lx, int rx, int l, int r) {
        
        if (lx>=r || rx<=l) return neutral;
        if (lx>=l && rx<=r) return tree[x];
        
        int mid=(lx+rx)/2;
        int a=calc(2*x+1,lx,mid,l,r),
        b=calc(2*x+2,mid,rx,l,r);
        return combine(a,b);
    }
    
    int query(int l, int r) {
        if (l>=r) return neutral;
        return calc(0,0,size,l,r);
    }
    
    void set(int i, int v) {
        
        put(size-1+i,v);
        update(0, 0, size, i);
        
    }
    
    void print() {
        
        cout<<"TREE: \n";
        int z=0;
        while (z<tree.size()) {
            for (int i=z; i<2*z+1; i++) cout<<tree[i]<<' ';
            cout<<'\n';
            z=z*2+1;
        }
        cout<<'\n';
        
    }
    
};

void solve() {
    
    int n; cin>>n;
    int m; cin>>m; 

    vii(a,n);
    vector<int> odd, even;
    forn(i,n) if (i%2) even.pb(a[i]); else odd.pb(a[i]);
    segtree est(even,0), ost(odd,0);

    forn(i,m) {

        int q;  cin>>q;
        if (q==1) {

            int i,v; cin>>i>>v;
            if (i%2) {
                ost.set((i-1)/2,v);
            } else {
                est.set((i-1)/2,v);
            }

        } else {

            int l,r; cin>>l>>r;
            if ((r+1-l)%2==0) {
                cout<<0<<'\n';
            } else {

                if (l%2) cout<<ost.query((l-1)/2,(r-1)/2+1)<<'\n';
                else cout<<est.query((l-1)/2,(r-1)/2+1)<<'\n';
            }

        }

    }

    //cout<<ans;

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //init_primes();
    
    int t=1;
    //cin>>t;
    
    while(t--) solve();
    
    paiu moment
}

Compilation message (stderr)

xoranges.cpp: In member function 'void segtree::print()':
xoranges.cpp:177:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |         while (z<tree.size()) {
      |                ~^~~~~~~~~~~~

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