NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#213936	#2380. 中位数	wanghanyu393	0	32ms	2880kb	C++11	1.5kb	2024-11-14 19:23:06	2024-11-14 23:03:00

answer

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 5;

int a[N];
int sum[N];
int b[N];
int n;

int tree[N * 2];
int lowbit(int x){
    return x & (-x);
}

void add(int x, int v){
	while(x <= 2 * n){
		tree[x] += v;
		x += lowbit(x);
	}
}

long long query(int x){
	long long cnt = 0;
	while(x > 0){
		cnt += tree[x];
		x -= lowbit(x);
	}
	return cnt;
}

bool check(int x){
    //cout << x << '\n';
    int ans = 0;
    memset(tree, 0, sizeof(tree));
    for(int i = 1; i <= n; i++){
        if(a[i] >= x) b[i] = 1;
        else b[i] = -1;
        sum[i] = sum[i - 1] + b[i];
    }
    add(n, 1);
    //cout << 1 << ' ';
    for(int i = 1; i <= n; i++){
        ans += query(sum[i] + n);
        //cout << query(sum[i] + n) << ' ';
        //cout << sum[i] + n << ' ';
        add(sum[i] + n, 1);
    }
    //for(int i = 1; i <= 2 * n; i++) cout << query(i) << ' ';
    //cout << '\n';
    //cout << ans << '\n';
    if((ans << 1) >= (n * (n + 1) >> 1)) return 1;
    return 0;
}

void solve(){
    cin >> n;
    int maxn = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], maxn = max(maxn, a[i]);
    int l = 1, r = maxn, ans = 0;
    while(l <= r){
        //cout << l << ' ' << r << '\n';
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << '\n';
}

signed main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

源文件, 语言: C++11

详细

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

Test #1:

score: 0

Wrong Answer

time: 0ms

memory: 2768kb

input:

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

output:

415196584

result:

wrong answer 1st numbers differ - expected: '411892743', found: '415196584'

Test #2:

score: 0

Wrong Answer

time: 4ms

memory: 2768kb

input:

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

output:

467261488

result:

wrong answer 1st numbers differ - expected: '451369372', found: '467261488'

Test #3:

score: 0

Wrong Answer

time: 4ms

memory: 2764kb

input:

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

output:

423293713

result:

wrong answer 1st numbers differ - expected: '420852999', found: '423293713'

Test #4:

score: 0

Wrong Answer

time: 8ms

memory: 2880kb

input:

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

output:

465584409

result:

wrong answer 1st numbers differ - expected: '465193387', found: '465584409'

Test #5:

score: 0

Wrong Answer

time: 8ms

memory: 2876kb

input:

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

output:

467006251

result:

wrong answer 1st numbers differ - expected: '466892796', found: '467006251'

Test #6:

score: 0

Wrong Answer

time: 8ms

memory: 2876kb

input:

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

output:

470684231

result:

wrong answer 1st numbers differ - expected: '470507384', found: '470684231'

Test #7:

score: 0

Runtime Error

input:

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

output:

result:

Test #8:

score: 0

Runtime Error

input:

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

output:

result:

Test #9:

score: 0

Runtime Error

input:

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

output:

result:

Test #10:

score: 0

Runtime Error

input:

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