oj.uz

Submission #645768

# Submission time Handle Problem Language Result Execution time Memory
645768 2022-09-28T00:29:09 Z kith14 Mountains (NOI20_mountains) C++17
2 / 100
 194 ms 27220 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 3e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], lr[N], rr[N], tree[N*4];
string s, s1, s2, ye = "YA", no = "TIDAK";
vector<pairll> v;

void input(){
  cin >> n;
  repp(i,1,n){
    cin >> ar[i];
    v.pb(mp(ar[i],i));
  }
  sort(v.begin(),v.end());
  ll pre = -1, cnt = 0;
  for (auto i : v){
    if (i.fr != pre){
      pre = i.fr;
      cnt++;
    }
    ar[i.sc] = cnt;
  }
}

void upd(ll l, ll r, ll idx, ll pos, ll val){
  if (l == r){
    tree[idx] = val;
    return;
  }
  ll md = (l+r)/2;
  if (pos <= md) upd(l,md,idx*2,pos,val);
  else upd(md+1,r,idx*2+1,pos,val);
  tree[idx] = tree[idx*2]+tree[idx*2+1];
}

ll que(ll l, ll r, ll idx, ll x, ll y){
  if (l > r || l > y || r < x) return 0;
  if (x <= l && r <= y) return tree[idx];
  ll md = (l+r)/2;
  return que(l,md,idx*2,x,y)+que(md+1,r,idx*2+1,x,y);
}

void solve(){
  memset(tree,0,sizeof(tree));
  repp(i,1,n){
    lr[i] = que(1,n,1,1,ar[i]-1);
    upd(1,n,1,ar[i],1);
  }

  memset(tree,0,sizeof(tree));
  repm(i,n,1){
    rr[i] = que(1,n,1,1,ar[i]-1);
    upd(1,n,1,ar[i],1);
  }

  ll ans = 0;
  repp(i,1,n){
    ans += lr[i]*rr[i];
  }
  cout << ans << endl;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 194 ms 27152 KB Output is correct
3 Correct 187 ms 27080 KB Output is correct
4 Correct 187 ms 27120 KB Output is correct
5 Correct 194 ms 27024 KB Output is correct
6 Correct 189 ms 27004 KB Output is correct
7 Correct 184 ms 27104 KB Output is correct
8 Correct 193 ms 27140 KB Output is correct
9 Correct 180 ms 27220 KB Output is correct
10 Correct 182 ms 27136 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9772 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 5 ms 9684 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9772 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 5 ms 9684 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 194 ms 27152 KB Output is correct
3 Correct 187 ms 27080 KB Output is correct
4 Correct 187 ms 27120 KB Output is correct
5 Correct 194 ms 27024 KB Output is correct
6 Correct 189 ms 27004 KB Output is correct
7 Correct 184 ms 27104 KB Output is correct
8 Correct 193 ms 27140 KB Output is correct
9 Correct 180 ms 27220 KB Output is correct
10 Correct 182 ms 27136 KB Output is correct
11 Incorrect 129 ms 22132 KB Output isn't correct
12 Halted 0 ms 0 KB -