oj.uz

Submission #734089

# Submission time Handle Problem Language Result Execution time Memory
734089 2023-05-01T16:27:51 Z vjudge1 Cryptography (NOI20_crypto) C++17
14 / 100
 1000 ms 110964 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

template<typename... T>
void see(T&... args) {((cin >> args), ...);}
template<typename... T>
void put(T&&... args) {((cout << args << ' '), ...);}
template<typename... T>
void putl(T&&... args) {((cout << args << ' '), ...); cout << '\n';}

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define F first
#define S second
#define ii pair<int, int>

#define vt vector
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz size()

#define endl '\n'

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define rev(i,b,a) for(int i=b; i>=a; i--)

#define reada(a,x,y) for(int i=x; i<=y; i++){cin >> a[i];}

const int M = 1e9+7;
const int Mxn = 1e6, Nxn = 2*1e5, Mxm = 3e5+5, Nxm = 1005, Dxn = 1e9+1;

int a[Mxm];
vt<int> t[4*Mxm];

void build(int id, int L, int R) {
    if(L == R) {
        t[id].pb(a[L]);
        return;
    }

    int mid = (L+R)/2;
    build(2*id, L, mid);
    build(2*id+1, mid+1, R);

    int n = t[2*id].sz, m = t[2*id+1].sz, i = 0, j = 0;

    while(i < n && j < m) {
        if(t[2*id][i] < t[2*id+1][j]) {
            t[id].pb(t[2*id][i]);
            i++;
        }
        else {
            t[id].pb(t[2*id+1][j]);
            j++;
        }
    }
    while(i < n) {
        t[id].pb(t[2*id][i]);
        i++;
    }
    while(j < m) {
        t[id].pb(t[2*id+1][j]);
        j++;
    }
}

int query(int id, int L, int R, int l, int r, int x) {
    if(L > r || R < l) return 0;
    if(l <= L && R <= r) {
        int n = t[id].sz;
        int k = upper_bound(all(t[id]), x) - t[id].begin();
        return k;
    }

    int mid = (L+R)/2;
    return query(2*id, L, mid, l, min(r, mid), x) + query(2*id+1, mid+1, R, max(l, mid+1), r, x);
}

int fact(int n) {
    if(n == 1) return 1;
    return (n * fact(n-1)) % M;
}

void solve() {
    int n; see(n);
    rep(i,1,n) see(a[i]);

    build(1, 1, n);

    int s = 0;
    rep(i,1,n-1) {
        s += ((query(1, 1, n, i+1, n, a[i]) * fact(n-i))) % M;
    }
    cout << s + 1;
    return;
}

signed main() { IOS
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
        cout << endl;
    }
    return 0;
}

Compilation message

Crypto.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int, long long int)':
Crypto.cpp:76:13: warning: unused variable 'n' [-Wunused-variable]
   76 |         int n = t[id].sz;
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 13 ms 28424 KB Output is correct
5 Correct 15 ms 28512 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 15 ms 28432 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 15 ms 28512 KB Output is correct
10 Correct 15 ms 28504 KB Output is correct
11 Correct 16 ms 28460 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 17 ms 28416 KB Output is correct
14 Correct 16 ms 28508 KB Output is correct
15 Correct 19 ms 28416 KB Output is correct
16 Correct 16 ms 28424 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 14 ms 28500 KB Output is correct
19 Correct 15 ms 28484 KB Output is correct
20 Correct 16 ms 28512 KB Output is correct
21 Correct 15 ms 28508 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct
23 Correct 14 ms 28520 KB Output is correct
24 Correct 15 ms 28404 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28388 KB Output is correct
2 Execution timed out 1082 ms 110964 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Execution timed out 1084 ms 110292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28624 KB Output is correct
2 Incorrect 39 ms 29064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 13 ms 28424 KB Output is correct
5 Correct 15 ms 28512 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 15 ms 28432 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 15 ms 28512 KB Output is correct
10 Correct 15 ms 28504 KB Output is correct
11 Correct 16 ms 28460 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 17 ms 28416 KB Output is correct
14 Correct 16 ms 28508 KB Output is correct
15 Correct 19 ms 28416 KB Output is correct
16 Correct 16 ms 28424 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 14 ms 28500 KB Output is correct
19 Correct 15 ms 28484 KB Output is correct
20 Correct 16 ms 28512 KB Output is correct
21 Correct 15 ms 28508 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct
23 Correct 14 ms 28520 KB Output is correct
24 Correct 15 ms 28404 KB Output is correct
25 Correct 14 ms 28624 KB Output is correct
26 Incorrect 39 ms 29064 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Execution timed out 1084 ms 110292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 13 ms 28424 KB Output is correct
5 Correct 15 ms 28512 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 15 ms 28432 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 15 ms 28512 KB Output is correct
10 Correct 15 ms 28504 KB Output is correct
11 Correct 16 ms 28460 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 17 ms 28416 KB Output is correct
14 Correct 16 ms 28508 KB Output is correct
15 Correct 19 ms 28416 KB Output is correct
16 Correct 16 ms 28424 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 14 ms 28500 KB Output is correct
19 Correct 15 ms 28484 KB Output is correct
20 Correct 16 ms 28512 KB Output is correct
21 Correct 15 ms 28508 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct
23 Correct 14 ms 28520 KB Output is correct
24 Correct 15 ms 28404 KB Output is correct
25 Correct 15 ms 28388 KB Output is correct
26 Execution timed out 1082 ms 110964 KB Time limit exceeded
27 Halted 0 ms 0 KB -