oj.uz

Submission #285515

# Submission time Handle Problem Language Result Execution time Memory
285515 2020-08-29T07:53:09 Z lukameladze Mountains (NOI20_mountains) C++14
6 / 100
 482 ms 10172 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);
    j=n+1;
    for (long long i=2; i<=n; i++)
    {
        if (fix[a[i].second]==1) 
        { j=i; break;}
        inc(a[i].second,1);
    }
    
    //cout<<j<<endl;
    for (long long 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 470 ms 10172 KB Output is correct
3 Correct 470 ms 9976 KB Output is correct
4 Correct 466 ms 9804 KB Output is correct
5 Correct 467 ms 9976 KB Output is correct
6 Correct 466 ms 9848 KB Output is correct
7 Correct 464 ms 9928 KB Output is correct
8 Correct 464 ms 9848 KB Output is correct
9 Correct 467 ms 9976 KB Output is correct
10 Correct 482 ms 9904 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 7672 KB Output is correct
2 Correct 125 ms 7564 KB Output is correct
3 Correct 123 ms 7544 KB Output is correct
4 Correct 117 ms 7544 KB Output is correct
5 Correct 120 ms 7544 KB Output is correct
6 Correct 119 ms 7672 KB Output is correct
7 Correct 117 ms 7544 KB Output is correct
8 Correct 102 ms 6392 KB Output is correct
9 Correct 103 ms 6392 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 117 ms 7672 KB Output is correct
2 Correct 125 ms 7564 KB Output is correct
3 Correct 123 ms 7544 KB Output is correct
4 Correct 117 ms 7544 KB Output is correct
5 Correct 120 ms 7544 KB Output is correct
6 Correct 119 ms 7672 KB Output is correct
7 Correct 117 ms 7544 KB Output is correct
8 Correct 102 ms 6392 KB Output is correct
9 Correct 103 ms 6392 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 149 ms 7544 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 1 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 384 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 1 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 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 7672 KB Output is correct
2 Correct 125 ms 7564 KB Output is correct
3 Correct 123 ms 7544 KB Output is correct
4 Correct 117 ms 7544 KB Output is correct
5 Correct 120 ms 7544 KB Output is correct
6 Correct 119 ms 7672 KB Output is correct
7 Correct 117 ms 7544 KB Output is correct
8 Correct 102 ms 6392 KB Output is correct
9 Correct 103 ms 6392 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 149 ms 7544 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 470 ms 10172 KB Output is correct
3 Correct 470 ms 9976 KB Output is correct
4 Correct 466 ms 9804 KB Output is correct
5 Correct 467 ms 9976 KB Output is correct
6 Correct 466 ms 9848 KB Output is correct
7 Correct 464 ms 9928 KB Output is correct
8 Correct 464 ms 9848 KB Output is correct
9 Correct 467 ms 9976 KB Output is correct
10 Correct 482 ms 9904 KB Output is correct
11 Correct 117 ms 7672 KB Output is correct
12 Correct 125 ms 7564 KB Output is correct
13 Correct 123 ms 7544 KB Output is correct
14 Correct 117 ms 7544 KB Output is correct
15 Correct 120 ms 7544 KB Output is correct
16 Correct 119 ms 7672 KB Output is correct
17 Correct 117 ms 7544 KB Output is correct
18 Correct 102 ms 6392 KB Output is correct
19 Correct 103 ms 6392 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Incorrect 149 ms 7544 KB Output isn't correct
22 Halted 0 ms 0 KB -