Submission #258754

#	Time	Username	Problem	Language	Result	Execution time	Memory
258754		ryangohca	Cryptography (NOI20_crypto)	C++17	100 / 100	296 ms	15340 KiB

Crypto

#include <bits/stdc++.h>
#define int long long
using namespace std;
int fw[300001];
int fact[300001];
const int N = 300000;
const int LOGN = log2(N) + 1;
const int MOD = 1000000007;
void update(int x, int v) {
    for (; x<=N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
vector<int> discretize(const vector<int>& V){
    vector<int> dis = V;
    vector<int> v(V.size());
    sort(dis.begin(), dis.end());
    dis.resize(unique(dis.begin(), dis.end()) - dis.begin());
    for (int i = 0; i < V.size(); i++){
        v[i] = lower_bound(dis.begin(), dis.end(), V[i]) - dis.begin() + 1;
    }
    return v;
}
main(){
  int n; cin >> n;
  vector<int> nums;
  fact[0] = 1;
  for (int i = 0; i < n; i++){
    int h; cin >> h;
    nums.push_back(h);
    update(i + 1, 1);
    fact[i+1] = fact[i] * (i + 1);
    fact[i+1] %= MOD;
  }
  nums = discretize(nums);
  int ans = 1;
  for (int i = 0; i < n; i++){
    int target = nums[i];
    ans += (sum(target) - 1) * fact[n - i - 1];
    ans %= MOD;
    update(target, -1);
  }
  cout << ans << endl;
}

Compilation message (stderr)

Crypto.cpp: In function 'std::vector<long long int> discretize(const std::vector<long long int>&)':
Crypto.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); i++){
                     ~~^~~~~~~~~~
Crypto.cpp: At global scope:
Crypto.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 21 / 21
• Subtask 6: 13 / 13
• Subtask 7: 19 / 19
• Subtask 8: 12 / 12