oj.uz

Submission #581082

# Submission time Handle Problem Language Result Execution time Memory
581082 2022-06-22T09:03:28 Z TimDee XORanges (eJOI19_xoranges) C++14
100 / 100
 154 ms 24648 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15892 KB Output is correct
3 Correct 8 ms 15972 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15944 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 9 ms 15976 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15892 KB Output is correct
3 Correct 8 ms 15972 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15944 KB Output is correct
6 Correct 7 ms 15948 KB Output is correct
7 Correct 9 ms 15976 KB Output is correct
8 Correct 7 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 10 ms 16136 KB Output is correct
12 Correct 9 ms 16188 KB Output is correct
13 Correct 11 ms 16160 KB Output is correct
14 Correct 10 ms 16256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 24552 KB Output is correct
2 Correct 140 ms 24648 KB Output is correct
3 Correct 137 ms 24632 KB Output is correct
4 Correct 141 ms 24572 KB Output is correct
5 Correct 110 ms 24564 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15892 KB Output is correct
3 Correct 8 ms 15972 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15944 KB Output is correct
6 Correct 7 ms 15948 KB Output is correct
7 Correct 9 ms 15976 KB Output is correct
8 Correct 7 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 10 ms 16136 KB Output is correct
12 Correct 9 ms 16188 KB Output is correct
13 Correct 11 ms 16160 KB Output is correct
14 Correct 10 ms 16256 KB Output is correct
15 Correct 127 ms 24552 KB Output is correct
16 Correct 140 ms 24648 KB Output is correct
17 Correct 137 ms 24632 KB Output is correct
18 Correct 141 ms 24572 KB Output is correct
19 Correct 110 ms 24564 KB Output is correct
20 Correct 154 ms 24000 KB Output is correct
21 Correct 116 ms 23976 KB Output is correct
22 Correct 126 ms 23972 KB Output is correct
23 Correct 111 ms 24548 KB Output is correct
24 Correct 123 ms 24548 KB Output is correct