oj.uz

Submission #734095

# Submission time Handle Problem Language Result Execution time Memory
734095 2023-05-01T16:40:15 Z vjudge1 Cryptography (NOI20_crypto) C++17
25 / 100
 312 ms 109992 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 f[Mxm];

void fact(int n) {
    f[1] = 1;
    for(int i = 2; i <= n; i++) {
        f[i] = f[i - 1] * i % M;
    }
}

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

    build(1, 1, n);
    fact(n);

    int s = 0;
    rep(i,1,n-1) {
        s += ((query(1, 1, n, i+1, n, a[i]) * f[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 15 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 15 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28468 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 16 ms 28512 KB Output is correct
10 Correct 17 ms 28500 KB Output is correct
11 Correct 16 ms 28512 KB Output is correct
12 Correct 16 ms 28432 KB Output is correct
13 Correct 16 ms 28388 KB Output is correct
14 Correct 16 ms 28516 KB Output is correct
15 Correct 17 ms 28500 KB Output is correct
16 Correct 15 ms 28508 KB Output is correct
17 Correct 16 ms 28628 KB Output is correct
18 Correct 14 ms 28468 KB Output is correct
19 Correct 16 ms 28484 KB Output is correct
20 Correct 17 ms 28460 KB Output is correct
21 Correct 16 ms 28500 KB Output is correct
22 Correct 16 ms 28500 KB Output is correct
23 Correct 19 ms 28500 KB Output is correct
24 Correct 16 ms 28472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28496 KB Output is correct
2 Incorrect 271 ms 108172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 261 ms 108084 KB Output is correct
3 Correct 264 ms 109836 KB Output is correct
4 Correct 271 ms 109864 KB Output is correct
5 Correct 265 ms 109860 KB Output is correct
6 Correct 312 ms 109828 KB Output is correct
7 Correct 251 ms 109864 KB Output is correct
8 Correct 266 ms 109992 KB Output is correct
9 Correct 258 ms 109736 KB Output is correct
10 Correct 262 ms 109904 KB Output is correct
11 Correct 265 ms 109864 KB Output is correct
12 Correct 262 ms 109864 KB Output is correct
13 Correct 254 ms 109744 KB Output is correct
14 Correct 253 ms 109856 KB Output is correct
15 Correct 260 ms 109828 KB Output is correct
16 Correct 269 ms 109860 KB Output is correct
17 Correct 259 ms 109736 KB Output is correct
18 Correct 262 ms 109860 KB Output is correct
19 Correct 253 ms 109864 KB Output is correct
20 Correct 274 ms 109864 KB Output is correct
21 Correct 249 ms 109872 KB Output is correct

Subtask #5
0 / 21.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28468 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 16 ms 28512 KB Output is correct
10 Correct 17 ms 28500 KB Output is correct
11 Correct 16 ms 28512 KB Output is correct
12 Correct 16 ms 28432 KB Output is correct
13 Correct 16 ms 28388 KB Output is correct
14 Correct 16 ms 28516 KB Output is correct
15 Correct 17 ms 28500 KB Output is correct
16 Correct 15 ms 28508 KB Output is correct
17 Correct 16 ms 28628 KB Output is correct
18 Correct 14 ms 28468 KB Output is correct
19 Correct 16 ms 28484 KB Output is correct
20 Correct 17 ms 28460 KB Output is correct
21 Correct 16 ms 28500 KB Output is correct
22 Correct 16 ms 28500 KB Output is correct
23 Correct 19 ms 28500 KB Output is correct
24 Correct 16 ms 28472 KB Output is correct
25 Correct 14 ms 28464 KB Output is correct
26 Incorrect 21 ms 29104 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 261 ms 108084 KB Output is correct
3 Correct 264 ms 109836 KB Output is correct
4 Correct 271 ms 109864 KB Output is correct
5 Correct 265 ms 109860 KB Output is correct
6 Correct 312 ms 109828 KB Output is correct
7 Correct 251 ms 109864 KB Output is correct
8 Correct 266 ms 109992 KB Output is correct
9 Correct 258 ms 109736 KB Output is correct
10 Correct 262 ms 109904 KB Output is correct
11 Correct 265 ms 109864 KB Output is correct
12 Correct 262 ms 109864 KB Output is correct
13 Correct 254 ms 109744 KB Output is correct
14 Correct 253 ms 109856 KB Output is correct
15 Correct 260 ms 109828 KB Output is correct
16 Correct 269 ms 109860 KB Output is correct
17 Correct 259 ms 109736 KB Output is correct
18 Correct 262 ms 109860 KB Output is correct
19 Correct 253 ms 109864 KB Output is correct
20 Correct 274 ms 109864 KB Output is correct
21 Correct 249 ms 109872 KB Output is correct
22 Correct 14 ms 28464 KB Output is correct
23 Incorrect 21 ms 29104 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28468 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 16 ms 28512 KB Output is correct
10 Correct 17 ms 28500 KB Output is correct
11 Correct 16 ms 28512 KB Output is correct
12 Correct 16 ms 28432 KB Output is correct
13 Correct 16 ms 28388 KB Output is correct
14 Correct 16 ms 28516 KB Output is correct
15 Correct 17 ms 28500 KB Output is correct
16 Correct 15 ms 28508 KB Output is correct
17 Correct 16 ms 28628 KB Output is correct
18 Correct 14 ms 28468 KB Output is correct
19 Correct 16 ms 28484 KB Output is correct
20 Correct 17 ms 28460 KB Output is correct
21 Correct 16 ms 28500 KB Output is correct
22 Correct 16 ms 28500 KB Output is correct
23 Correct 19 ms 28500 KB Output is correct
24 Correct 16 ms 28472 KB Output is correct
25 Correct 16 ms 28496 KB Output is correct
26 Incorrect 271 ms 108172 KB Output isn't correct
27 Halted 0 ms 0 KB -