Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
3654 | 2021-12-25 17:49:46 | ewu_ieee21_user_34 | Find MinMaxXoR Number | C++ 11 | 262 ms | 23896 kb | Wrong Answer - 9 |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 12 ms | 19036 kb | 1 | Accepted | |||||||
2 | 15 ms | 19052 kb | 1 | Accepted | |||||||
3 | 13 ms | 18968 kb | 1 | Accepted | |||||||
4 | 12 ms | 18976 kb | 1 | Accepted | |||||||
5 | 13 ms | 19016 kb | 1 | Accepted | |||||||
6 | 13 ms | 19084 kb | 1 | Accepted | |||||||
7 | 32 ms | 19624 kb | 1 | Accepted | |||||||
8 | 31 ms | 19604 kb | 1 | Accepted | |||||||
9 | 262 ms | 23896 kb | 0 | Wrong Answer | |||||||
10 | 0 ms | 0 kb | 0 | Skipped | |||||||
11 | 0 ms | 0 kb | 0 | Skipped | |||||||
12 | 0 ms | 0 kb | 0 | Skipped | |||||||
13 | 0 ms | 0 kb | 0 | Skipped | |||||||
14 | 0 ms | 0 kb | 0 | Skipped | |||||||
15 | 0 ms | 0 kb | 0 | Skipped | |||||||
16 | 0 ms | 0 kb | 0 | Skipped |
Source Code
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <typename num_t> using ordered_set = tree<num_t,null_type,less<num_t>,rb_tree_tag,tree_order_statistics_node_update>; const int DEBUGGER = 0; #define io ios_base::sync_with_stdio(0); cin.tie(NULL) #define mset(a,v) memset(a,v,sizeof(a)) #define lp(i,a,n) for(int i=a;i<n;i++) #define lpr(i,a,n) for(int i=n-1;i>=a;i--) #define stlp(it,stl) for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();it++) #define stlpr(it,stl) for(__typeof(stl.rbegin()) it=stl.rbegin();it!=stl.rend();it++) #define r(a) a.begin(),a.end() #define II ({ ll TEMP; cin>>TEMP; TEMP; }) #define SI ({ string TEMP; cin>>TEMP; TEMP; }) #define AI(a) ({ int n=sizeof(a)/sizeof(a[0]); lp(I,0,n)a[I]=II; }) #define AO(a) ({ int n=sizeof(a)/sizeof(a[0]); lp(I,0,n){cout<<(I?" ":"")<<a[I];} if(DEBUGGER)cout<<endl;else cout<<'\n'; }) #define VI(v) ({ lp(I,0,v.size())v[I]=II; }) #define VO(v) ({ lp(I,0,v.size()){cout<<(I?" ":"")<<v[I];} if(DEBUGGER)cout<<endl;else cout<<'\n'; }) #define outa(a) ({ if(DEBUGGER)dbg(a); else cout<<a<<'\n'; }) #define dbg(a) ({ if(DEBUGGER)cout<<#a<<" = "<<a<<endl; }) #define cbit(n,p) ((n)&(1LL<<(p))) #define sbit(n,p) ((n)|(1LL<<(p))) #define tbit(n,p) ((n)^(1LL<<(p))) #define F first #define S second typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vl; const ll MAX = 5e5+5; const ll MOD = 1e9+7; const ll INF = 9e18; const double PI = 3.141592653589793238462; ll addM(ll a,ll b){return (a+=b)>=MOD?(a-=MOD):a;} ll subM(ll a,ll b){return (a-=b)<0?(a+=MOD):a;} ll n,a[MAX],mxvis[2][(ll)1e6+6]; pll trN[4*MAX]; void combine(pll &trP,pll &trL,pll &trR){ trP={max(trL.F,trR.F),min(trL.S,trR.S)}; } void init(int n,int l,int r){ if(l==r) return void(trN[n]={a[l],a[l]}); int m=(l+r)/2; init(2*n,l,m); init(2*n+1,m+1,r); combine(trN[n],trN[2*n],trN[2*n+1]); } ll query(int n,int l,int r,int i,int j,int c,int d,ll val){ if(j<i) return 0; if(j<l || r<i) return -1; if(i<=l && r<=j){ if(trN[n].S>=val && c==0 && mxvis[0][val]<a[i])return r-l+1; if(trN[n].S>val && c==0 && mxvis[0][val]>a[i])return r-l+1; if(trN[n].F<=val && c==1 && mxvis[1][val]<a[i])return r-l+1; if(trN[n].F<val && c==1 && mxvis[1][val]>a[i])return r-l+1; if(l==r) return 0; } int m=(l+r)/2; ll trQL=0,trQR=0; if(d==0){ trQR=query(2*n+1,m+1,r,i,j,c,d,val); if(trQR==min(r,j)-max(m+1,i)+1 || trQR==-1) trQL=query(2*n,l,m,i,j,c,d,val); } else{ trQL=query(2*n,l,m,i,j,c,d,val); if(trQL==min(m,j)-max(l,i)+1 || trQL==-1) trQR=query(2*n+1,m+1,r,i,j,c,d,val); } trQL=max(trQL,0LL); trQR=max(trQR,0LL); return trQL+trQR; } void solve(){ mset(mxvis,-1); n=II; lp(i,1,n+1)a[i]=II; init(1,1,n); ll ans=0; lp(i,1,n+1){ ll minleftsz=query(1,1,n,1,i-1,0,0,a[i]); ll minrightsz=query(1,1,n,i+1,n,0,1,a[i]); ll maxleftsz=query(1,1,n,1,i-1,1,0,a[i]); ll maxrightsz=query(1,1,n,i+1,n,1,1,a[i]); ll minsubarrsz=(minleftsz+1)*(minrightsz+1)-1; if(minsubarrsz&1)ans^=a[i]; mxvis[0][a[i]]=i+minrightsz; ll maxsubarrsz=(maxleftsz+1)*(maxrightsz+1)-1; if(maxsubarrsz&1)ans^=a[i]; mxvis[1][a[i]]=i+maxrightsz; dbg(minleftsz<<' '<<minrightsz<<' '<<maxleftsz<<' '<<maxrightsz<<' '<<a[i]); dbg(minsubarrsz<<' '<<maxsubarrsz); } outa(ans); } int main(void){ io; int multipletest=0; if(multipletest){ int tc; cin>>tc; while(tc--) solve(); } else solve(); return 0; }