oj.uz

Submission #285512

# Submission time Handle Problem Language Result Execution time Memory
285512 2020-08-29T07:49:48 Z lukameladze Mountains (NOI20_mountains) C++14
6 / 100
 490 ms 15284 KB 
# 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -