Submission #843609

#	Time	Username	Problem	Language	Result	Execution time	Memory
843609		Esgeer	XORanges (eJOI19_xoranges)	C++17	100 / 100	94 ms	14244 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vll vector<ll>
#define vvll vector<vll>
#define vb vector<bool>
#define vvb vector<vb>
#define endl "\n"
#define sp << " " <<
#define debug cout << "Working!" << endl; return;
#define F(i, s, n) for(int i = s; i < n; i++)
#define pb push_back
int inf = (~(1ll << (sizeof(int) * 8 - 1))) >> 1;
int mod = 1e9 + 7;
 
int add(int x, int y) {
    int sum ((x % mod) + (y % mod));
    if(sum >= mod) return sum - mod;
    else return sum;
}
int sadd(int x, int y) {
    return (x + y >= mod ? x + y - mod : x + y);
}
 
string FILENAME = "";
void setIO() {
    ios::sync_with_stdio(0); cin.tie(0);
    if(FILENAME == "") {
        #ifdef Local
            freopen("in.txt", "r", stdin);
            freopen("out.txt", "w", stdout);
        #endif
    } else {
        freopen((FILENAME + ".in").c_str(), "r", stdin);
        freopen((FILENAME + ".out").c_str(), "w", stdin);
    }
}

const int N = 1e5;
int a1[N], a2[N], t1[N*4], t2[N*4];
int build1(int node, int l, int r) {
    if(l == r) return t1[node] = a1[l];
    int m = (l + r) >> 1;
    return t1[node] = (build1(node*2, l, m) ^ build1(node*2+1, m+1, r));
}
int build2(int node, int l, int r) {
    if(l == r) return t2[node] = a2[l];
    int m = (l + r) >> 1;
    return t2[node] = (build2(node*2, l, m) ^ build2(node*2+1, m+1, r));
}
int query1(int node, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return t1[node];
    int m = (l + r) >> 1;
    return (query1(node*2, l, m, L, R) ^ query1(node*2+1, m+1, r, L, R));
}
int query2(int node, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return t2[node];
    int m = (l + r) >> 1;
    return (query2(node*2, l, m, L, R) ^ query2(node*2+1, m+1, r, L, R));
}
void update1(int node, int l, int r, int idx, int val) {
    if(l > idx || r < idx) return;
    if(l == r) { t1[node] = val; return; }
    int m = (l + r) / 2;
    update1(node*2, l, m, idx, val);
    update1(node*2+1, m+1, r, idx, val);
    t1[node] = t1[node*2] ^ t1[node*2+1];
}
void update2(int node, int l, int r, int idx, int val) {
    if(l > idx || r < idx) return;
    if(l == r) { t2[node] = val; return; }
    int m = (l + r) / 2;
    update2(node*2, l, m, idx, val);
    update2(node*2+1, m+1, r, idx, val);
    t2[node] = t2[node*2] ^ t2[node*2+1];
}

void solve() {
    int n, q;
    cin >> n >> q;
    F(i, 0, (n+1)/2) {
        cin >> a1[i];
        if((n&1) == 0 || i < n/2) cin >> a2[i];
    }
    int n1 = (n+1)/2, n2 = n/2;
    build1(1, 0, n1-1);
    build2(1, 0, n2-1);
    F(i, 0, q) {
        int type;
        cin >> type;
        if(type == 2) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            int len = r - l + 1;
            if((len & 1) == 0) {
                cout << 0 << endl;
                continue;
            }
            if(l & 1) {
                cout << query2(1, 0, n2-1, l/2, r/2) << endl;
            } else {
                cout << query1(1, 0, n1-1, l/2, r/2) << endl;
            }
        } else {
            int i, v;
            cin >> i >> v;
            i--;
            if(i & 1) {
                update2(1, 0, n1-1, i/2, v);
            } else {
                update1(1, 0, n1-1, i/2, v);
            }
        }
    }
}
 
signed main() {
    setIO();
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

xoranges.cpp: In function 'void setIO()':
xoranges.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((FILENAME + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((FILENAME + ".out").c_str(), "w", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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