Submission #6712727


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,20);
 	wm.shoki2();
 	sort(ve.begin(),ve.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<<20);
 		int a2=wm.range_count(x+1,n,y+1,1<<20);
 		int a3=i-a1;
 	
 		int a4=n-1-a1-a2-a3;
 	//	cout<<i<<" "<<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 600
Code Size 18872 Byte
Status AC
Exec Time 1043 ms
Memory 125164 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 26
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 AC 4 ms 4352 KB
02.txt AC 4 ms 4352 KB
03.txt AC 4 ms 4352 KB
04.txt AC 4 ms 4352 KB
05.txt AC 4 ms 4352 KB
06.txt AC 4 ms 4352 KB
07.txt AC 4 ms 4352 KB
08.txt AC 4 ms 4352 KB
09.txt AC 4 ms 4352 KB
10.txt AC 4 ms 4352 KB
11.txt AC 990 ms 123884 KB
12.txt AC 955 ms 121196 KB
13.txt AC 997 ms 124652 KB
14.txt AC 927 ms 117356 KB
15.txt AC 1003 ms 123244 KB
16.txt AC 1007 ms 124652 KB
17.txt AC 1035 ms 125036 KB
18.txt AC 1043 ms 124780 KB
19.txt AC 844 ms 125164 KB
20.txt AC 801 ms 119788 KB
21.txt AC 879 ms 123756 KB
22.txt AC 879 ms 122988 KB
23.txt AC 4 ms 4352 KB
s1.txt AC 4 ms 4352 KB
s2.txt AC 4 ms 4352 KB
s3.txt AC 4 ms 4352 KB