oj.uz

Submission #596570

# Submission time Handle Problem Language Result Execution time Memory
596570 2022-07-14T20:37:24 Z AdamGS Cryptography (NOI20_crypto) C++17
15 / 100
 228 ms 25308 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define all(a) a.begin(), a.end()
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7, LIM=3e5+7;
int T[LIM], S[LIM], tr[4*LIM], N=1;
ll sil[LIM];
map<int,int>mp;
void upd(int v) {
  for(v+=N; v; v/=2) --tr[v];
}
ll cnt(int l, int r) {
  l+=N; r+=N;
  ll ans=tr[l];
  if(l!=r) ans+=tr[r];
  while(l/2!=r/2) {
    if(l%2==0) ans+=tr[l+1];
    if(r%2==1) ans+=tr[r-1];
    l/=2; r/=2;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  sil[0]=1;
  for(ll i=1; i<LIM; ++i) sil[i]=(sil[i-1]*i)%MOD;
  int n;
  cin >> n;
  while(N<n) N*=2;
  rep(i, n) {
    cin >> T[i];
    S[i]=T[i];
    tr[N+i]=1;
  }
  for(int i=N-1; i; --i) tr[i]=tr[2*i]+tr[2*i+1];
  sort(S, S+n);
  rep(i, n) mp[S[i]]=i;
  ll ans=1;
  rep(i, n) {
    ans=(ans+sil[cnt(0, mp[T[i]])-1]*(cnt(0, mp[T[i]])-1))%MOD;
    upd(mp[T[i]]);
  }
  cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Incorrect 3 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2684 KB Output is correct
2 Correct 218 ms 25224 KB Output is correct
3 Correct 218 ms 25240 KB Output is correct
4 Correct 212 ms 25228 KB Output is correct
5 Correct 215 ms 25232 KB Output is correct
6 Correct 218 ms 25228 KB Output is correct
7 Correct 213 ms 25116 KB Output is correct
8 Correct 213 ms 25252 KB Output is correct
9 Correct 217 ms 25276 KB Output is correct
10 Correct 211 ms 25168 KB Output is correct
11 Correct 214 ms 25108 KB Output is correct
12 Correct 228 ms 25236 KB Output is correct
13 Correct 228 ms 25220 KB Output is correct
14 Correct 219 ms 25160 KB Output is correct
15 Correct 227 ms 25232 KB Output is correct
16 Correct 213 ms 25224 KB Output is correct
17 Correct 218 ms 25308 KB Output is correct
18 Correct 224 ms 25228 KB Output is correct
19 Correct 220 ms 25228 KB Output is correct
20 Correct 225 ms 25220 KB Output is correct
21 Correct 228 ms 25224 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Incorrect 224 ms 24224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Incorrect 6 ms 2868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Incorrect 3 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Incorrect 224 ms 24224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Incorrect 3 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -