当前位置: 代码迷 >> 综合 >> Codeforces Round #496 (Div. 3) E题 Median on Segments (Permutations Edition)
  详细解决方案

Codeforces Round #496 (Div. 3) E题 Median on Segments (Permutations Edition)

热度:22   发布时间:2023-11-06 17:40:12.0

看了一个上午的官方英语题解,实在是太难理解了,主要是英语看不懂,最后自己想了办法,从m往回走记录了比m大和比m小的元素个数差值, 然后再往m的右边走,寻找左边能与之构成符合要求数列的个数,会爆int,cf评测很人性,爆了还有提醒数据溢出。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map> 
#define ls 2*rt
#define rs 2*rt+1
#define lson ls,L,mid
#define rson rs,mid+1,R
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f;
/*void dis(int a[], int n){printf("总数为%d个\n",n); for(int i = 0; i < n; i++) 	cout<<a[i]<<", ";cout<<endl<<"------------------"<<endl;		
}*/const int mx = 2e5+10;
map<int,int>ma;
int p[mx];
int n,m;
int main(){//int T=10;scanf("%d%d",&n,&m);for(int i = 0; i< n; i++)scanf("%d",p+i);int pos= 0;for(int i = 0; i < n; i++){if(p[i] == m){pos = i;break;}	} ma[0] = 1;int te= 0; for(int i = pos-1; i >= 0; i--){if(p[i] > m)te++;elsete--;ma[te]++;}ll ans= 0;ans +=  ma[0] + ma[1];te = 0;for(int i = pos+1; i < n; i++){if(p[i] > m)te++;elsete--;ans += ma[-te] + ma[1-te];} cout<<ans<<endl;return 0;
}

  相关解决方案