QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#572948#9313. Make Maxcrush_jzhRE 0ms0kbC++141.8kb2024-09-18 16:55:062024-09-18 16:55:08

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 16:55:08]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-18 16:55:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define  int long long
const int N=2e5+9;
struct node{
    int num,times;
};
node arr[N];
int head[N];
int tail[N];
int sum[N];
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>arr[i].num;
            arr[i].times=1;
            tail[i]=i+1;
            head[i]=i-1;
        }
        head[1]=-1;
        tail[n]=-1;
        int x=2;
        while(x!=-1&&x>0)
        {
            if(arr[head[x]].num==arr[x].num)
            {
                arr[head[x]].times+=arr[x].times;
                tail[head[x]]=tail[x];
                head[tail[x]]=head[x];
                x=tail[x];
            }
            if(arr[head[x]].num>arr[x].num&&arr[tail[x]].num>arr[x].num)
            {
                if(arr[head[x]].num>arr[tail[x]].num)
                {
                    arr[tail[x]].times+=arr[x].times;
                    head[tail[x]]=head[x];
                    tail[head[x]]=tail[x];
                    x=tail[x];
                    break;
                }
                if(arr[head[x]].num<arr[tail[x]].num)
                {
                    arr[head[x]].times+=arr[x].times;
                    head[tail[x]]=head[x];
                    tail[head[x]]=tail[x];
                    x=head[x];
                }
            }
            x=tail[x];
        }
        x=1;
        int ans=0;
        while(tail[x]!=-1)
        {
            arr[x].times+=arr[head[x]].times;
            ans+=arr[x].times;
            x=tail[x];
        }
        cout<<ans<<'\n';
    }
    system("pause");
    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

4
2
1 2
2
2 2
7
1 1 1 2 2 2 2
3
1 2 3

output:


result: