Submission #6707811


Source Code Expand

Copy
   #include <bits/stdc++.h>
 
//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-10)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
 
                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[2200010];
                int inv[2200010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
 
                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
                
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
//    mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
      
       
       
                               //----------------kokomade tenpure------------
 
 
// verify
// CF 813E
// JAG夏2018 day3D
// yukicoder 738 743
// AOJ 1549



// wavlet_matrix wm;
// wm.shoki1(ve,d)   <- 数列を表す vector とビット数 d つまりすべての項やクエリは1<<d 未満
// wm.shoki2()
// 
// 個数だけでなく和をも必要な時は3か所のコメントアウトを外す

struct BV{//O(n) words O(1) time
	
	private:
	public:
	int N;
	vector<int> RAN;
	vector<int> SEL1;
	vector<int> SEL0;
	int k0=0,k1=0;
	vector<bool> VEC;
	void shoki1(int NN){
		
		N=NN;
		
		VEC.resize(N,false);
		RAN.resize(N+1,0);
		
		
	}
	void setbit(int i){
		VEC[i]=1;
	}
	void resetbit(int i){
		VEC[i]=0;
	}
	void shoki2(){
		for(int i=0;i<N;i++){
			if(VEC[i]){
				RAN[i]=k1;
				k1++;
			}
			else{
				RAN[i]=k0;
				k0++;
			}
		}
		SEL1.resize(k1);
		SEL0.resize(k0);
		k0=0,k1=0;
		for(int i=0;i<N;i++){
			if(VEC[i]){
				SEL1[k1]=i;
				k1++;
			}
			else{
				SEL0[k0]=i;
				k0++;
			}
		}
	}
	
	
	int rank(int it){ return RAN[it];}
	int rank0(int it){
		if(it==N) return k0;
		if(VEC[it])return it-RAN[it];
		else return RAN[it];
	}
	int rank1(int it){
		if(it==N) return k1;
		if(VEC[it]==0)return it-RAN[it];
		else return RAN[it];
	}
	int select(int ko,bool b){
		if(b){
			if(ko>=k1)return -1;
			else return SEL1[ko];
		}
		else{
			if(ko>=k0)return -1;
			else return SEL0[ko];
		}
	}
	int access(int it) {return VEC[it];}

};

struct wavlet_matrix{
	private:
	public:
	
	int N;
	
	vector<int> VEC;
	int d;
	
	vector<BV> bv;
	vector<int> zero;
	
	//vector<vector<int>> rui;
	
	void shoki1(vector<int> &input,int D){
		VEC=input;
		N=input.size();
		d=D;
		bv.resize(d);
		zero.resize(d);
		/*
		/////////////////////////////////////////////////////////////
		rui.resize(d);
		/////////////////////////////////////////////////////////////
		*/
	}
	void shoki2(){
		
		for(int i=d-1;i>=0;i--){
			
			bv[i].shoki1(N);
			vector<int> mae,ato;
			for(int j=0;j<N;j++){
			
				if(VEC[j]&(1ll<<i)){
					
					ato.pb(VEC[j]);
					bv[i].setbit(j);
				}
				else{
					mae.pb(VEC[j]);
				}
			}
			
			zero[i]=(int)mae.size();
			bv[i].shoki2();
			
			mae.insert(mae.end(),ato.begin(),ato.end());
			
			/*
			/////////////////////////////////////////////////////////////
			rui[i]=mae;
			for(int j=1;j<N;j++)rui[i][j]+=rui[i][j-1];
			/////////////////////////////////////////////////////////////
			*/
			
			
			swap(VEC,mae);
		}
		
	}
	
	
	int access(int r){
		int ans=0;
		for(int i=d-1;i>=0;i--){
			if(bv[i].access(r)){
				ans+=(1ll<<i);
				r=zero[i]+bv[i].rank(r);
			}
			else{
				r=bv[i].rank(r);
			}
		}
		
		return ans;
	}
	
	int range_rank(int val, int l,int r){ // [l,r) にあるvalの個数
		
		
		
		for(int i=d-1;i>=0;i--){
			if(val&(1ll<<i)){
				r=zero[i]+bv[i].rank1(r);
				l=zero[i]+bv[i].rank1(l);
			}
			else{
				r=bv[i].rank0(r);
				l=bv[i].rank0(l);
			}
			
			
			if(l>=r) return 0;
		}
	
	return r-l;
	}
	
	int rank(int val,int pos){// 0,1,...,pos にあるvalの個数
		return range_rank(val,0,pos+1);
	}
	
	int select(int val,int kth){// kth 番目の valの位置 無いなら-1
		
		
		int l=0,r=N;
		for(int i=d-1;i>=0;i--){
			if(val&(1ll<<i)){
				r=zero[i]+bv[i].rank1(r);
				l=zero[i]+bv[i].rank1(l);
			}
			else{
				r=bv[i].rank0(r);
				l=bv[i].rank0(l);
			}
			
			
			if(l+kth>=r) return -1;
		}
		int pos=l+kth;
		//cout<<" "<<pos<<" "<<endl;;
		for(int i=0;i<d;i++){
			if(val&(1ll<<(i))){
			
				pos=bv[i].select(pos-zero[i],1);
			}
			else{
				pos=bv[i].select(pos,0);
			}
	//		cout<<pos<<endl;
		}
		return pos;
		
	}
	
	int x_th_min(int x,int l,int r){
		//区間[l,r)で小さいほうからk番目の値
		// 0 <= x < r-l
		// 0 <= l < r <= N
		int ans=0;
		
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			int z=t2-t1;
		//	cout<<x<<" "<<l<<" "<<r<<" "<<ans<<endl;
			if(z>x){
				l=t1,r=t2;
			}
			else{
				ans+=(1ll<<i);
				x-=z;
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
		}
		return ans;
	}
	
	int range_min(int l,int r){
		return x_th_min(0,l,r);
	}
	
	int range_max(int l,int r){
		return x_th_min(r-l-1,l,r);
	}
	
	
	int range_count_prefix(int l,int r,int val){
		//区間[l,r)に存在する値が[0,val)な項の個数
		if(val<=0) return 0;
		if(l>=r)return 0;
		val--;
		//[0,val]に変更
		int ans=0;
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			
			if(val&(1ll<<i)){
				ans+=t2-t1;				
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1;
				r=t2;
			}
		}
		ans+=r-l;
		
		return ans;
		
	}
	
	int range_count(int l,int r,int vl,int vr){
		//区間[l,r)に存在する値が[vl,vr)な項の個数
		if(vr<=vl) return 0;
		if(r<=l) return 0;
		return range_count_prefix(l,r,vr)-range_count_prefix(l,r,vl);
		
	}		
	
	
	int range_bound_max(int l,int r,int val){
		//区間[l,r)に存在する値がval以下の中で最大の値
		//該当しない場合は -1
		
		if(l>=r) return -1;
		
		int dep=-1;
		int cl=-1;
		int cr=-1;
		int cur=0;
		
		int ima=0;
		for(int i=d-1;i>=0;i--){
			
			if(i==0){
				if(val&1){
					if(l<r){
						dep=0;
						cl=l,cr=r;
						cur=ima;
					}
				}
				else{
					int t1=bv[i].rank0(l);
					int t2=bv[i].rank0(r);
					if(t1<t2) return ima;
				}
				break;
				
			}
			
			if(val&(1ll<<i)){
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				if(t1!=t2){
					dep=i-1;
					cl=t1,cr=t2;
					cur=ima;
				}
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
				ima+=(1ll<<i);
			}
			else{
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				l=t1,r=t2;
				
			}
		}
		if(dep==-1) return -1;
		ima=cur;
		l=cl,r=cr;
		for(int i=dep;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			if(r-l>t2-t1){
				ima+=(1ll<<i);
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1,r=t2;
			}
		}
		
		return ima;
	}
	
	
	int range_bound_min(int l,int r,int val){
		//区間[l,r)に存在する値がval以上の中で最小の値
		//該当しない場合は -1
		if(l>=r) return -1;
		
		int dep=-1;
		int cl=-1;
		int cr=-1;
		int cur=0;
		
		int ima=0;
		for(int i=d-1;i>=0;i--){
			
			if(i==0){
				if((val&1)==0){
					if(l<r){
						dep=0;
						cl=l,cr=r;
						cur=ima;
					}
				}
				else{
					int t1=zero[i]+l-bv[i].rank0(l);
					int t2=zero[i]+r-bv[i].rank0(r);
					ima+=(1ll<<i);
					if(t1<t2) return ima;
				}
				break;
				
			}
			
			if((val&(1ll<<i))==0){
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				int s1=zero[i]+l-t1;
				int s2=zero[i]+r-t2;
				if(s1<s2){
					dep=i-1;
					cl=s1,cr=s2;
					cur=ima+(1ll<<i);
				}
				l=t1,r=t2;
			}
			else{
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				int s1=zero[i]+l-t1;
				int s2=zero[i]+r-t2;
				l=s1,r=s2;
				ima=ima+(1ll<<i);
				
			}
		}
	
		if(dep==-1) return -1;
		ima=cur;
		l=cl,r=cr;
		
		for(int i=dep;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			if(t2-t1==0){
				ima+=(1ll<<i);
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1,r=t2;
			}
			assert(l<r);
		}
		
		return ima;
	}
	
	
			/////////////////////////////////////////////////////////////
	/*
	int range_sum_prefix(int l,int r,int val){
		//区間[l,r)に存在する値が[0,val)な項の和
		if(val<=0) return 0;
		if(l>=r)return 0;
		val--;
		//[0,val]に変更
		int ans=0;
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			
			if(val&(1ll<<i)){
				ans+=(t2>0?rui[i][t2-1]:0)-(t1>0?rui[i][t1-1]:0);
				
				l=zero[i]+l-t1;;
				r=zero[i]+r-t2;
			}
			else{
				l=t1;
				r=t2;
			}
			
		}
		
		ans-=(l>0?rui[0][l-1]:0)-(r>0?rui[0][r-1]:0);
		
		return ans;
		
	}
	
	int range_sum(int l,int r,int vl,int vr){
		//区間[l,r)に存在する値が[vl,vr)な項の和
		
		if(vr<=vl) return 0;
		if(r<=l) return 0;
		return range_sum_prefix(l,r,vr)-range_sum_prefix(l,r,vl);
		
	}
	*/
			/////////////////////////////////////////////////////////////
};

int ni[400020];
wavlet_matrix wm;
 signed main(){
 	
 
    	       cin.tie(0);
   			ios::sync_with_stdio(false);

 	mod=998244353;
 	map<int,int>mx,my;
 	ni[0]=1;
 	for(int i=1;i<=400000;i++)ni[i]=ni[i-1]*2%mod;
 	
 	vector<pa> ve;
set<int> sex,sey; 	
 	int n;
 	cin>>n;
 	for(int i=0;i<n;i++){
 		int X,Y;
 		cin>>X>>Y;
 		sex.insert(X);
 		sey.insert(Y);
 		
 		ve.pb(mp(X,Y));
 	}
 	int cnt=0;
 	for(auto it=sex.begin();it!=sex.end();it++){
 		mx[*it]=cnt;
 		cnt++;
 	}
 	cnt=0;
 	for(auto it=sey.begin();it!=sey.end();it++){
 		my[*it]=cnt;
 		cnt++;
 	}
 	for(auto &v:ve){
 		v.first=mx[v.first];
 		v.second=my[v.second];
 	}
 	
 	int ans=0;
 	
 	vector<int> V(n);
 	for(auto v:ve){
 		
 		int vx=v.first,vy=v.second;
 		v=mp(vx,vy);
 		V[vx]=vy;
 	}
 	
 	wm.shoki1(V,30);
 	wm.shoki2();
 	sort(V.begin(),V.end());
 	for(int i=0;i<n;i++){
 		pa v=ve[i];
 		int x=v.first,y=v.second;
 		
 		int a1=wm.range_count(0,x,y+1,1<<30);
 		int a2=wm.range_count(x+1,n,y+1,1<<30);
 		int a3=i-a1;
 	
 		int a4=n-1-a1-a2-a3;
 	//	cout<<a1<<" "<<a2<<" "<<a3<<" "<<a4<<endl;
 	//	assert(a1+a2+a3+a4==n-1);
 		
 		ans+=ni[n-1];
 		ans%=mod;
 		{ 			
 			int c=1;
 			c*=ni[a1]+mod-1;
 			c%=mod;
 			c*=ni[a2]+mod-1;
 			c%=mod;
 			c*=ni[a3]+mod-1;
 			c%=mod; 			
 			c*=ni[a4]+mod-1;
 			c%=mod; 			
 			ans+=c;
 	//		cout<<c<<endl;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a2]+mod-1;
 			c%=mod;
 			c*=ni[a3]+mod-1;
 			c%=mod; 			
 			c*=ni[a4]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a1]+mod-1;
 			c%=mod;
 			c*=ni[a3]+mod-1;
 			c%=mod; 			
 			c*=ni[a4]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a1]+mod-1;
 			c%=mod;
 			c*=ni[a2]+mod-1;
 			c%=mod;
 			c*=ni[a4]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a1]+mod-1;
 			c%=mod;
 			c*=ni[a2]+mod-1;
 			c%=mod;
 			c*=ni[a3]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a2]+mod-1;
 			c%=mod;
 			c*=ni[a3]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 		{ 			
 			int c=1;
 			c*=ni[a1]+mod-1;
 			c%=mod;
 			c*=ni[a4]+mod-1;
 			c%=mod; 			
 			ans+=c;
 		}
 	//	cout<<ans<<endl;
 		ans%=mod;
 		
 	}
 	cout<<ans<<endl;
 	
 	return 0;
 
  }
 

Submission Info

Submission Time
Task F - Enclosed Points
User smiken
Language C++14 (GCC 5.4.1)
Score 0
Code Size 18860 Byte
Status RE
Exec Time 845 ms
Memory 157932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
WA × 1
AC × 3
WA × 11
RE × 12
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt WA 4 ms 4352 KB
02.txt WA 4 ms 4352 KB
03.txt WA 4 ms 4352 KB
04.txt WA 4 ms 4352 KB
05.txt WA 4 ms 4352 KB
06.txt WA 4 ms 4352 KB
07.txt WA 4 ms 4352 KB
08.txt WA 4 ms 4352 KB
09.txt WA 4 ms 4352 KB
10.txt WA 4 ms 4352 KB
11.txt RE 814 ms 155628 KB
12.txt RE 795 ms 150124 KB
13.txt RE 817 ms 156524 KB
14.txt RE 767 ms 147948 KB
15.txt RE 845 ms 157932 KB
16.txt RE 819 ms 157676 KB
17.txt RE 831 ms 157548 KB
18.txt RE 838 ms 155884 KB
19.txt RE 741 ms 156268 KB
20.txt RE 725 ms 152300 KB
21.txt RE 790 ms 156908 KB
22.txt RE 810 ms 157420 KB
23.txt AC 4 ms 4352 KB
s1.txt AC 4 ms 4352 KB
s2.txt AC 4 ms 4352 KB
s3.txt WA 4 ms 4352 KB