oj.uz

Submission #734096

# Submission time Handle Problem Language Result Execution time Memory
734096 2023-05-01T16:41:36 Z vjudge1 Cryptography (NOI20_crypto) C++17
25 / 100
 286 ms 108044 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%M;
    }

    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)) % M;
}

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 14 ms 28500 KB Output is correct
2 Correct 14 ms 28392 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 14 ms 28392 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 14 ms 28464 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28472 KB Output is correct
7 Correct 14 ms 28464 KB Output is correct
8 Correct 14 ms 28484 KB Output is correct
9 Correct 14 ms 28504 KB Output is correct
10 Correct 16 ms 28380 KB Output is correct
11 Correct 15 ms 28460 KB Output is correct
12 Correct 15 ms 28464 KB Output is correct
13 Correct 14 ms 28484 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct
16 Correct 14 ms 28500 KB Output is correct
17 Correct 15 ms 28500 KB Output is correct
18 Correct 15 ms 28500 KB Output is correct
19 Correct 15 ms 28500 KB Output is correct
20 Correct 15 ms 28500 KB Output is correct
21 Correct 15 ms 28500 KB Output is correct
22 Correct 18 ms 28500 KB Output is correct
23 Correct 14 ms 28480 KB Output is correct
24 Correct 14 ms 28500 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Incorrect 281 ms 108004 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 14 ms 28388 KB Output is correct
2 Correct 269 ms 107832 KB Output is correct
3 Correct 265 ms 108032 KB Output is correct
4 Correct 267 ms 107936 KB Output is correct
5 Correct 261 ms 107848 KB Output is correct
6 Correct 262 ms 108024 KB Output is correct
7 Correct 260 ms 107796 KB Output is correct
8 Correct 265 ms 107848 KB Output is correct
9 Correct 263 ms 107828 KB Output is correct
10 Correct 264 ms 107920 KB Output is correct
11 Correct 269 ms 107924 KB Output is correct
12 Correct 263 ms 107896 KB Output is correct
13 Correct 286 ms 107856 KB Output is correct
14 Correct 268 ms 107956 KB Output is correct
15 Correct 262 ms 107860 KB Output is correct
16 Correct 269 ms 107952 KB Output is correct
17 Correct 260 ms 107924 KB Output is correct
18 Correct 266 ms 107860 KB Output is correct
19 Correct 265 ms 107912 KB Output is correct
20 Correct 269 ms 107852 KB Output is correct
21 Correct 268 ms 108044 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Incorrect 18 ms 29012 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 14 ms 28392 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 14 ms 28464 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28472 KB Output is correct
7 Correct 14 ms 28464 KB Output is correct
8 Correct 14 ms 28484 KB Output is correct
9 Correct 14 ms 28504 KB Output is correct
10 Correct 16 ms 28380 KB Output is correct
11 Correct 15 ms 28460 KB Output is correct
12 Correct 15 ms 28464 KB Output is correct
13 Correct 14 ms 28484 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct
16 Correct 14 ms 28500 KB Output is correct
17 Correct 15 ms 28500 KB Output is correct
18 Correct 15 ms 28500 KB Output is correct
19 Correct 15 ms 28500 KB Output is correct
20 Correct 15 ms 28500 KB Output is correct
21 Correct 15 ms 28500 KB Output is correct
22 Correct 18 ms 28500 KB Output is correct
23 Correct 14 ms 28480 KB Output is correct
24 Correct 14 ms 28500 KB Output is correct
25 Correct 16 ms 28500 KB Output is correct
26 Incorrect 18 ms 29012 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 28388 KB Output is correct
2 Correct 269 ms 107832 KB Output is correct
3 Correct 265 ms 108032 KB Output is correct
4 Correct 267 ms 107936 KB Output is correct
5 Correct 261 ms 107848 KB Output is correct
6 Correct 262 ms 108024 KB Output is correct
7 Correct 260 ms 107796 KB Output is correct
8 Correct 265 ms 107848 KB Output is correct
9 Correct 263 ms 107828 KB Output is correct
10 Correct 264 ms 107920 KB Output is correct
11 Correct 269 ms 107924 KB Output is correct
12 Correct 263 ms 107896 KB Output is correct
13 Correct 286 ms 107856 KB Output is correct
14 Correct 268 ms 107956 KB Output is correct
15 Correct 262 ms 107860 KB Output is correct
16 Correct 269 ms 107952 KB Output is correct
17 Correct 260 ms 107924 KB Output is correct
18 Correct 266 ms 107860 KB Output is correct
19 Correct 265 ms 107912 KB Output is correct
20 Correct 269 ms 107852 KB Output is correct
21 Correct 268 ms 108044 KB Output is correct
22 Correct 16 ms 28500 KB Output is correct
23 Incorrect 18 ms 29012 KB Output isn't correct
24 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 14 ms 28392 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 14 ms 28464 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28472 KB Output is correct
7 Correct 14 ms 28464 KB Output is correct
8 Correct 14 ms 28484 KB Output is correct
9 Correct 14 ms 28504 KB Output is correct
10 Correct 16 ms 28380 KB Output is correct
11 Correct 15 ms 28460 KB Output is correct
12 Correct 15 ms 28464 KB Output is correct
13 Correct 14 ms 28484 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct
16 Correct 14 ms 28500 KB Output is correct
17 Correct 15 ms 28500 KB Output is correct
18 Correct 15 ms 28500 KB Output is correct
19 Correct 15 ms 28500 KB Output is correct
20 Correct 15 ms 28500 KB Output is correct
21 Correct 15 ms 28500 KB Output is correct
22 Correct 18 ms 28500 KB Output is correct
23 Correct 14 ms 28480 KB Output is correct
24 Correct 14 ms 28500 KB Output is correct
25 Correct 13 ms 28500 KB Output is correct
26 Incorrect 281 ms 108004 KB Output isn't correct
27 Halted 0 ms 0 KB -