UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185084#2380. 中位数snow_trace1001093ms11676kbC++111.4kb2023-09-21 11:54:432023-09-21 12:24:39

answer

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
int ps[300005];
int a[300005],tree[700010],tong[600006];
int b[300005];
int n;
void upd(int pos,int add){
	for(int i = pos;i<2*n+5;i+=lowbit(i))tree[i]+=add;
}int query(int pos){int res =0 ;
	for(int i = pos;i>0;i-=lowbit(i))res+=tree[i];return res;
}bool check(int x){
	long long tot = 0,s =0,l = ((long long)n*(n+1)/2+1)/2;
	for(int i =0;i<2*n+5;i++)tree[i] = tong[i] = 0;
	int pos = 0;
	for(int i = 1;i<=n;i++){
		if(a[i] == x)b[i] = 0,pos= i;
		if(a[i]<x)b[i] = -1;
		if(a[i]>x)b[i] = 1;
	}int xx = n+1;
	for(int i = 1;i<=n;i++){
		upd(s+xx,1);s+=b[i];
		tot=tot+query(xx+s-1);
	//	cout << s << " " << tot << endl;
	}s = 0;
	for(int i = 1;i<=pos;i++)s+=b[i];tong[s+x]++;
	for(int i = pos+1;i<=n;i++)s+=b[i],tong[s+x]++;s=0;
	for(int i =0;i<pos;i++){
		s+=b[i];tot+=tong[x+s];
	}//cout << x << " " << tot << " " << l << endl;
	return (tot>=l);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i<=n;i++)cin >>a[i];
	vector<pair<int,int> >p;
	for(int i =1;i<=n;i++)p.push_back({a[i],i});
	sort(p.begin(),p.end());
	for(int i =0;i<p.size();i++)a[p[i].second] = i+1,ps[i+1] = p[i].first;
	int l = 1,r = n;
	while(l<r){
		int mid = l+r+1>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}cout << ps[l] << endl;
}/*
20
9 14 19 20 2 2 9 13 10 15 20 3 16 7 9 19 1 2 14 1 
*/

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1276kb

input:

200
247837946 222748444 549404903 934970141 181690491 116150147 755881953 912914845 578004877 589768...

output:

411892743

result:

ok 1 number(s): "411892743"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

200
504553675 321343511 781936447 172776833 779139954 643752948 106 164 303976944 828799931 11502170...

output:

451369372

result:

ok 1 number(s): "451369372"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

200
738368650 91602659 340556191 835209882 409442204 656938221 258295858 90658347 126689369 56196859...

output:

420852999

result:

ok 1 number(s): "420852999"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1516kb

input:

5000
300051244 685920750 122806687 315801142 33592358 339985437 262520930 380010194 687330910 550362...

output:

465193387

result:

ok 1 number(s): "465193387"

Test #5:

score: 10
Accepted
time: 3ms
memory: 1516kb

input:

5000
108135249 950186870 146626753 682580494 744412491 4159 995071655 157947560 668940645 878891308 ...

output:

466892796

result:

ok 1 number(s): "466892796"

Test #6:

score: 10
Accepted
time: 3ms
memory: 1512kb

input:

5000
246610103 780664789 678774940 716124165 518453378 300121008 135383319 939869983 430946660 13412...

output:

470507384

result:

ok 1 number(s): "470507384"

Test #7:

score: 10
Accepted
time: 279ms
memory: 11672kb

input:

300000
786856547 380253059 684225515 795392038 881780483 18437791 793783577 832330260 801624996 3466...

output:

463539280

result:

ok 1 number(s): "463539280"

Test #8:

score: 10
Accepted
time: 266ms
memory: 11676kb

input:

300000
951000485 930070933 3566360 157114366 150196488 611226665 123590886 950624066 472150346 57976...

output:

462334620

result:

ok 1 number(s): "462334620"

Test #9:

score: 10
Accepted
time: 281ms
memory: 11676kb

input:

300000
728509094 406128756 696166390 756254976 31403187 672131182 35544213 870708756 3659210 5227553...

output:

464162969

result:

ok 1 number(s): "464162969"

Test #10:

score: 10
Accepted
time: 261ms
memory: 11676kb

input:

300000
804874490 52247250 546638789 400214210 383796618 47995083 814777769 507157584 466189162 28296...

output:

463577194

result:

ok 1 number(s): "463577194"

Extra Test:

score: 0
Extra Test Passed