oj.uz

Submission #402891

# Submission time Handle Problem Language Result Execution time Memory
402891 2021-05-12T13:15:10 Z Fidisk Mountains (NOI20_mountains) C++14
24 / 100
 449 ms 9884 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;

struct segtree_ele{
    int val,l,r;
} segtree[10000009];

ll res;
int sizet,l[400009],a[400009],n,i,cnt;
vector<pll> g;

int getnode(int &x) {
    if (x==0) {
        sizet++;
        x=sizet;
        segtree[x]={0,0,0};
    }
    return x;
}

void update(int id,int l,int r,int u) {
    if (l>r||r<u||l>u) {
        return;
    }
    if (l==u&&r==u) {
        segtree[id].val++;
        return;
    }
    int mid=(r+l)/2;
    if (mid<u) {
        update(getnode(segtree[id].r),mid+1,r,u);
    }
    else {
        update(getnode(segtree[id].l),l,mid,u);
    }
    segtree[id].val=segtree[getnode(segtree[id].l)].val+segtree[getnode(segtree[id].r)].val;
}

int get(int id,int l,int r,int u,int v) {
    if (l>r||r<u||l>v) {
        return 0;
    }
    if (u<=l&&r<=v) {
        return segtree[id].val;
    }
    int mid=(r+l)/2;
    return get(getnode(segtree[id].l),l,mid,u,v)+get(getnode(segtree[id].r),mid+1,r,u,v);
}

int main(){
    IO;
    cin>>n;
    g.push_back({-1,0});
    for (i=1;i<=n;i++) {
        cin>>a[i];
        g.push_back({a[i],i});
    }
    sort(g.begin(),g.end());
    for (i=1;i<=n;i++) {
        if (g[i].fi!=g[i-1].fi) {
            cnt++;
        }
        a[g[i].se]=cnt;
    }
    sizet=0;
    getnode(a[0]);
    for (i=1;i<=n;i++) {
        //cout<<a[i]<<' ';
        l[i]=get(1,1,maxn,1,a[i]-1);
        update(1,1,maxn,a[i]);
    }
    //cout<<'\n';
    sizet=0;
    a[0]=0;
    getnode(a[0]);
    for (i=n;i>=1;i--) {
        //cout<<l[i]<<' '<<get(1,1,maxn,1,a[i]-1)<<'\n';
        res+=ll(l[i])*ll(get(1,1,maxn,1,a[i]-1));
        update(1,1,maxn,a[i]);
    }
    cout<<res<<'\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 127 ms 8640 KB Output is correct
3 Correct 132 ms 8684 KB Output is correct
4 Correct 128 ms 8640 KB Output is correct
5 Correct 127 ms 8640 KB Output is correct
6 Correct 127 ms 8640 KB Output is correct
7 Correct 127 ms 8640 KB Output is correct
8 Correct 131 ms 8640 KB Output is correct
9 Correct 130 ms 8580 KB Output is correct
10 Correct 127 ms 8640 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 9604 KB Output is correct
2 Correct 215 ms 9664 KB Output is correct
3 Correct 224 ms 9664 KB Output is correct
4 Correct 225 ms 9664 KB Output is correct
5 Correct 220 ms 9680 KB Output is correct
6 Correct 215 ms 9656 KB Output is correct
7 Correct 224 ms 9616 KB Output is correct
8 Correct 203 ms 9664 KB Output is correct
9 Correct 200 ms 9640 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 9604 KB Output is correct
2 Correct 215 ms 9664 KB Output is correct
3 Correct 224 ms 9664 KB Output is correct
4 Correct 225 ms 9664 KB Output is correct
5 Correct 220 ms 9680 KB Output is correct
6 Correct 215 ms 9656 KB Output is correct
7 Correct 224 ms 9616 KB Output is correct
8 Correct 203 ms 9664 KB Output is correct
9 Correct 200 ms 9640 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 301 ms 9768 KB Output is correct
12 Correct 301 ms 9684 KB Output is correct
13 Correct 322 ms 9680 KB Output is correct
14 Correct 303 ms 9664 KB Output is correct
15 Correct 304 ms 9672 KB Output is correct
16 Correct 300 ms 9624 KB Output is correct
17 Correct 303 ms 9628 KB Output is correct
18 Correct 248 ms 9656 KB Output is correct
19 Correct 245 ms 9692 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 9604 KB Output is correct
2 Correct 215 ms 9664 KB Output is correct
3 Correct 224 ms 9664 KB Output is correct
4 Correct 225 ms 9664 KB Output is correct
5 Correct 220 ms 9680 KB Output is correct
6 Correct 215 ms 9656 KB Output is correct
7 Correct 224 ms 9616 KB Output is correct
8 Correct 203 ms 9664 KB Output is correct
9 Correct 200 ms 9640 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 301 ms 9768 KB Output is correct
12 Correct 301 ms 9684 KB Output is correct
13 Correct 322 ms 9680 KB Output is correct
14 Correct 303 ms 9664 KB Output is correct
15 Correct 304 ms 9672 KB Output is correct
16 Correct 300 ms 9624 KB Output is correct
17 Correct 303 ms 9628 KB Output is correct
18 Correct 248 ms 9656 KB Output is correct
19 Correct 245 ms 9692 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 417 ms 9724 KB Output is correct
22 Correct 408 ms 9688 KB Output is correct
23 Correct 449 ms 9656 KB Output is correct
24 Correct 427 ms 9884 KB Output is correct
25 Correct 410 ms 9652 KB Output is correct
26 Correct 403 ms 9716 KB Output is correct
27 Correct 411 ms 9668 KB Output is correct
28 Correct 288 ms 9652 KB Output is correct
29 Correct 286 ms 9688 KB Output is correct
30 Correct 1 ms 204 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 127 ms 8640 KB Output is correct
3 Correct 132 ms 8684 KB Output is correct
4 Correct 128 ms 8640 KB Output is correct
5 Correct 127 ms 8640 KB Output is correct
6 Correct 127 ms 8640 KB Output is correct
7 Correct 127 ms 8640 KB Output is correct
8 Correct 131 ms 8640 KB Output is correct
9 Correct 130 ms 8580 KB Output is correct
10 Correct 127 ms 8640 KB Output is correct
11 Correct 221 ms 9604 KB Output is correct
12 Correct 215 ms 9664 KB Output is correct
13 Correct 224 ms 9664 KB Output is correct
14 Correct 225 ms 9664 KB Output is correct
15 Correct 220 ms 9680 KB Output is correct
16 Correct 215 ms 9656 KB Output is correct
17 Correct 224 ms 9616 KB Output is correct
18 Correct 203 ms 9664 KB Output is correct
19 Correct 200 ms 9640 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 301 ms 9768 KB Output is correct
22 Correct 301 ms 9684 KB Output is correct
23 Correct 322 ms 9680 KB Output is correct
24 Correct 303 ms 9664 KB Output is correct
25 Correct 304 ms 9672 KB Output is correct
26 Correct 300 ms 9624 KB Output is correct
27 Correct 303 ms 9628 KB Output is correct
28 Correct 248 ms 9656 KB Output is correct
29 Correct 245 ms 9692 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Incorrect 1 ms 332 KB Output isn't correct
32 Halted 0 ms 0 KB -