Submission #13852525


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int L[202020],R[202020];
int S[2][402020];

int ok1(int v,int tar) {
	int C[3]={};
	int i;
	FOR(i,N) {
		if(R[i]<v) C[0]++;
		else if(v<L[i]) C[2]++;
		else C[1]++;
	}
	
	return C[0]<tar;
}

int ok2(int v,int tar) {
	int C[3]={};
	int i;
	FOR(i,N) {
		if(R[i]<v) C[0]++;
		else if(v<L[i]) C[2]++;
		else C[1]++;
	}
	
	return C[2]<tar;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> V;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		V.push_back(L[i]);
		V.push_back(R[i]+1);
	}
	
	int ma[2]={};
	int mi[2]={1<<30,1<<30};
	FOR(i,2) {
		int tar;
		if(N%2==0) {
			tar=N/2+i;
		}
		else {
			tar=(N+1)/2;
		}
		
		for(j=29;j>=0;j--) {
			if(ok1(ma[i]+(1<<j),tar)) ma[i]+=1<<j;
			if(ok2(mi[i]-(1<<j),tar)) mi[i]-=1<<j;
		}
	}
	
	//cout<<mi[0]<<" "<<mi[1]<<" "<<ma[0]<<" "<<ma[1]<<endl;
	if(N%2==0) {
		cout<<(ma[1]+ma[0]-mi[0]-mi[1])+1<<endl;
	}
	else {
		cout<<ma[0]-mi[0]+1<<endl;
	}
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

Submission Info

Submission Time
Task E - Count Median
User kmjp
Language C++ (GCC 9.2.1)
Score 500
Code Size 1669 Byte
Status AC
Exec Time 104 ms
Memory 6616 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:44:10: warning: unused variable ‘k’ [-Wunused-variable]
   44 |  int i,j,k,l,r,x,y; string s;
      |          ^
./Main.cpp:44:12: warning: unused variable ‘l’ [-Wunused-variable]
   44 |  int i,j,k,l,r,x,y; string s;
      |            ^
./Main.cpp:44:14: warning: unused variable ‘r’ [-Wunused-variable]
   44 |  int i,j,k,l,r,x,y; string s;
      |              ^
./Main.cpp:44:16: warning: unused variable ‘x’ [-Wunused-variable]
   44 |  int i,j,k,l,r,x,y; string s;
      |                ^
./Main.cpp:44:18: warning: unused variable ‘y’ [-Wunused-variable]
   44 |  int i,j,k,l,r,x,y; string s;
      |                  ^
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:7:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:87:38: note: in expansion of macro ‘FOR’
   87 |  FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
      |                                      ^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status AC
AC × 25
Set Name Test Cases
Sample
All handmade02, handmade03, handmade04, handmade05, handmade06, handmade07, handmade08, handmade09, handmade10, handmade11, handmade12, handmade13, handmade14, handmade15, handmade16, handmade17, random18, random19, random20, random21, random22, random23, random24, sample00, sample01
Case Name Status Exec Time Memory
handmade02 AC 7 ms 3616 KB
handmade03 AC 2 ms 3460 KB
handmade04 AC 2 ms 3464 KB
handmade05 AC 2 ms 3576 KB
handmade06 AC 2 ms 3576 KB
handmade07 AC 2 ms 3624 KB
handmade08 AC 2 ms 3464 KB
handmade09 AC 1 ms 3504 KB
handmade10 AC 2 ms 3576 KB
handmade11 AC 2 ms 3620 KB
handmade12 AC 49 ms 6504 KB
handmade13 AC 49 ms 6428 KB
handmade14 AC 94 ms 6592 KB
handmade15 AC 95 ms 6592 KB
handmade16 AC 58 ms 6616 KB
handmade17 AC 55 ms 6436 KB
random18 AC 25 ms 3964 KB
random19 AC 56 ms 5028 KB
random20 AC 101 ms 6452 KB
random21 AC 104 ms 6556 KB
random22 AC 2 ms 3584 KB
random23 AC 60 ms 4932 KB
random24 AC 51 ms 4708 KB
sample00 AC 4 ms 3584 KB
sample01 AC 2 ms 3564 KB