NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #200092 | #2700. 数列 | xiaopangfeiyu | 100 | 79ms | 24596kb | C++11 | 4.2kb | 2023-12-28 09:13:47 | 2023-12-28 13:54:40 |
answer
/*
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/_/_/_/ _/ _/_/_/_/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/ _/_/_/_/_/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
#include <bits/stdc++.h>
#define REN 1000000
#define MAXN (REN+5)
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') {f=-1;} c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n,m;
int a[MAXN];
map<pair<int,int>,pair<int,int>>t;
int ans;
int minsum[MAXN],maxsum[MAXN];
int calc(int L,int R,int minn,int maxx)
{
// cout<<L<<' '<<R<<' '<<minn<<' '<<maxx<<'\n';
int i;
minsum[L]=(a[L]==minn);
for(i=L+1;i<=R;i++)
{
minsum[i]=minsum[i-1]+(a[i]==minn);
}
maxsum[R]=(a[R]==maxx);
for(i=R-1;i>=L;i--)
{
maxsum[i]=maxsum[i+1]+(a[i]==maxx);
}
int res=1e9;
for(i=L;i<=R-1;i++)
{
res=min(res,minsum[i]+maxsum[i+1]);
}
res=min(res,minsum[R]);
res=min(res,maxsum[L]);
// cout<<res<<'\n';
return res;
}
signed main()
{
// freopen("1.in","r",stdin);
int i,j,k;
n=read();
int minn=1e9;
int maxx=0;
for(i=1;i<=n;i++)
{
a[i]=read();
maxx=max(maxx,a[i]-minn);
minn=min(minn,a[i]);
}
int minid=0;minn=1e9;
int maxid=0;
for(i=1;i<=n;i++)
{
if(a[i]-minn==maxx) {maxid=i;}
if(a[i]<minn)
{
if(a[maxid]-minn==maxx)
{
ans+=calc(minid,maxid,minn,a[maxid]);
}
minid=i;
minn=a[i];
}
}
if(a[maxid]-minn==maxx)
{
ans+=calc(minid,maxid,minn,a[maxid]);
}
cout<<ans;
return 0;
}
/*
8
4 6 1 1 3 1 3 3
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/ _/_/_/ _/ _/ _/_/_/ _/
_/_/_/_/_/ _/_/ _/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
详细
小提示：点击横条可展开更详细的信息
Subtask #1:
score: 24
Accepted
Test #1:
score: 24
Accepted
time: 0ms
memory: 1172kb
input:
20 123333333 100000000 123333333 100000000 100000000 100000000 100000000 -46629627 -46629627 -466296...
output:
2
result:
ok single line: '2'
Subtask #2:
score: 16
Accepted
Test #2:
score: 16
Accepted
time: 0ms
memory: 1172kb
input:
100 100000000 123333333 123333333 123333333 123333333 123333333 123333333 100000000 123333333 100000...
output:
24
result:
ok single line: '24'
Subtask #3:
score: 21
Accepted
Test #3:
score: 21
Accepted
time: 0ms
memory: 1288kb
input:
5000 123333333 100000000 123333333 100000000 123333333 100000000 100000000 109260380 100000000 10778...
output:
1424
result:
ok single line: '1424'
Subtask #4:
score: 39
Accepted
Test #4:
score: 39
Accepted
time: 7ms
memory: 3508kb
input:
100000 107584386 100000000 117570850 100000000 100000000 100000000 123333333 113985760 100000000 100...
output:
32140
result:
ok single line: '32140'
Test #5:
score: 0
Accepted
time: 72ms
memory: 24596kb
input:
1000000 100000000 116429445 123333333 109196270 123333333 111215733 100000000 100000000 100000000 10...
output:
328969
result:
ok single line: '328969'
Extra Test:
score: 0
Extra Test Passed
