답안 #285512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285512	2020-08-29T07:49:48 Z	lukameladze	Mountains (NOI20_mountains)	C++14	6 / 100	490 ms	15284 KB

Mountains

# include <bits/stdc++.h>
using namespace std;
long long tree[1000005],j,n,ans,x,y,id,fix[300005],raod;
pair <long long , long long > a[300005];
void inc(int idx, int val)
{
    for (int i=idx; i<=n; i+=i&(-i))
    {
        tree[i]+=val;
    }
}
long long getans (int idx)
{
    long  long pas=0;
    for (int i=idx; i>0; i-=i&(-i))
    {
        pas+=tree[i];
    }
    return pas;
}
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for (int i=1; i<=n; i++)
    {
        if(a[i].first!=a[i-1].first) 
        fix[a[i].second]=1;//cout<<i<<" ";
    }
   // cout<<endl;
    inc(a[1].second,1);
    for (int i=2; i<=n; i++)
    {
        if (fix[a[i].second]==1) 
        { j=i; break;}
        inc(a[i].second,1);
    }
    for (int i=j; i<=n; i++)
    {
        raod++;
        id=a[i].second;
        x=getans(id-1);
        y=getans(n)-getans(id);
       // cout<<id<<" "<<x<<" "<<y<<" "<<x*y<<endl;
        ans+=x*y;
        if (fix[a[i+1].second]==1)
        {
        inc(a[i].second,raod);
        raod=0;
        }
    }
    cout<<ans<<endl;
}

Subtask #1

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	471 ms	12356 KB	Output is correct
3	Correct	480 ms	15284 KB	Output is correct
4	Correct	480 ms	15224 KB	Output is correct
5	Correct	472 ms	15180 KB	Output is correct
6	Correct	468 ms	15172 KB	Output is correct
7	Correct	489 ms	15284 KB	Output is correct
8	Correct	472 ms	15228 KB	Output is correct
9	Correct	490 ms	15232 KB	Output is correct
10	Correct	473 ms	15216 KB	Output is correct

Subtask #2

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	7520 KB	Output is correct
2	Correct	126 ms	7940 KB	Output is correct
3	Correct	122 ms	7928 KB	Output is correct
4	Correct	124 ms	8056 KB	Output is correct
5	Correct	133 ms	7888 KB	Output is correct
6	Correct	131 ms	7928 KB	Output is correct
7	Correct	122 ms	7896 KB	Output is correct
8	Correct	103 ms	6784 KB	Output is correct
9	Correct	104 ms	6792 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct

Subtask #3

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	7520 KB	Output is correct
2	Correct	126 ms	7940 KB	Output is correct
3	Correct	122 ms	7928 KB	Output is correct
4	Correct	124 ms	8056 KB	Output is correct
5	Correct	133 ms	7888 KB	Output is correct
6	Correct	131 ms	7928 KB	Output is correct
7	Correct	122 ms	7896 KB	Output is correct
8	Correct	103 ms	6784 KB	Output is correct
9	Correct	104 ms	6792 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Incorrect	165 ms	8280 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Incorrect	1 ms	388 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Incorrect	1 ms	388 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	7520 KB	Output is correct
2	Correct	126 ms	7940 KB	Output is correct
3	Correct	122 ms	7928 KB	Output is correct
4	Correct	124 ms	8056 KB	Output is correct
5	Correct	133 ms	7888 KB	Output is correct
6	Correct	131 ms	7928 KB	Output is correct
7	Correct	122 ms	7896 KB	Output is correct
8	Correct	103 ms	6784 KB	Output is correct
9	Correct	104 ms	6792 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Incorrect	165 ms	8280 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #7

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	471 ms	12356 KB	Output is correct
3	Correct	480 ms	15284 KB	Output is correct
4	Correct	480 ms	15224 KB	Output is correct
5	Correct	472 ms	15180 KB	Output is correct
6	Correct	468 ms	15172 KB	Output is correct
7	Correct	489 ms	15284 KB	Output is correct
8	Correct	472 ms	15228 KB	Output is correct
9	Correct	490 ms	15232 KB	Output is correct
10	Correct	473 ms	15216 KB	Output is correct
11	Correct	115 ms	7520 KB	Output is correct
12	Correct	126 ms	7940 KB	Output is correct
13	Correct	122 ms	7928 KB	Output is correct
14	Correct	124 ms	8056 KB	Output is correct
15	Correct	133 ms	7888 KB	Output is correct
16	Correct	131 ms	7928 KB	Output is correct
17	Correct	122 ms	7896 KB	Output is correct
18	Correct	103 ms	6784 KB	Output is correct
19	Correct	104 ms	6792 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	165 ms	8280 KB	Output isn't correct
22	Halted	0 ms	0 KB	-