oj.uz

Submission #226585

# Submission time Handle Problem Language Result Execution time Memory
226585 2020-04-24T12:45:49 Z Theo830 XORanges (eJOI19_xoranges) C++17
100 / 100
 149 ms 11128 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(long long i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
const long long N = 2e5+5;
vll visit,dist,taken;
vector<vll> adj;
vector<vii> adj2;
priority_queue<ii,vector<ii>, greater<ii> > pq;
ll bit[N][2];
ll siz;
ll res = 0;
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll power(ll a,ll b){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
void BITup(ll k, ll x,ll pos){while(k <= siz){bit[k][pos]^=x;k += k & -k;}}
ll BITq(ll k,ll pos){ll s=0;while(k>=1){s^=bit[k][pos];k -= k &-k;}return s;}
struct node{ll lazy=0,val=0;}seg[4000000];
struct poll{ll x,y;};
void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
void filesin(void){freopen("a.txt","r",stdin);}
void filesout(void){freopen("a.out","w",stdout);}
int main(void){
    fastio;
    ll n,q
    c(n);
    c(q);
    ll arr[n];
    arrin(arr,n);
    siz = n+5;
    f(i,0,n+5){
        f(j,0,2){
            bit[i][j] = 0;
        }
    }
    f(i,0,n){
        BITup(i+1,arr[i],(i+1)%2);
    }
    w(q){
        ll d;
        c(d);
        ll l,r;
        c(l);
        c(r);
        if(d == 1){
            BITup(l,arr[l-1],l%2);
            BITup(l,r,l%2);
            arr[l-1] = r;
        }
        else{
            if((r-l+1) % 2 == 1){
                pl((BITq(r,l%2) ^ BITq(l-1,l%2)));
            }
            else{
                pl(0);
            }
        }
    }
}
/*
3 3
1 2 3
2 1 3
1 1 3
2 1 3

5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4
*/

Compilation message

xoranges.cpp: In function 'void filesin()':
xoranges.cpp:51:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesin(void){freopen("a.txt","r",stdin);}
                    ~~~~~~~^~~~~~~~~~~~~~~~~~~
xoranges.cpp: In function 'void filesout()':
xoranges.cpp:52:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesout(void){freopen("a.out","w",stdout);}
                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 436 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6268 KB Output is correct
2 Correct 123 ms 11128 KB Output is correct
3 Correct 149 ms 11128 KB Output is correct
4 Correct 120 ms 10744 KB Output is correct
5 Correct 112 ms 10748 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 436 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 114 ms 6268 KB Output is correct
16 Correct 123 ms 11128 KB Output is correct
17 Correct 149 ms 11128 KB Output is correct
18 Correct 120 ms 10744 KB Output is correct
19 Correct 112 ms 10748 KB Output is correct
20 Correct 138 ms 10872 KB Output is correct
21 Correct 123 ms 10872 KB Output is correct
22 Correct 142 ms 10872 KB Output is correct
23 Correct 121 ms 10748 KB Output is correct
24 Correct 118 ms 10744 KB Output is correct