oj.uz

Submission #867804

# Submission time Handle Problem Language Result Execution time Memory
867804 2023-10-29T13:37:44 Z sleepntsheep Pilot (NOI19_pilot) C++17
5 / 100
 1000 ms 12628 KB 
#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 1000005
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")


int n, q;
array<int, 2> a[N], b[N];
set<int> s;
ll z, c[N], fw[N];
inline ll C2(ll x) { return x*(x+1)/2; }

inline int upd(int p) { for (;p<N;p=p|(p+1)) ++fw[p]; return p; }
inline int qry(int p) { int z=0; for (;p;p=(p&(p+1))-1)z+=fw[p];return z; }
inline int search(int k)
{
    int p = 0, s = 0;
    for (int j=21;j--;) if (p+(1<<j)<N && s+fw[p+(1<<j)]<=k) s += fw[p+=1<<j];
    return p+1;
}

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i][0], a[i][1] = i + 2;
    for (int i = 0; i < q; ++i) cin >> b[i][0], b[i][1] = i;
    upd(1); upd(n+2);
    sort(a, a+n);
    sort(b, b+q);
    z = C2(n);
    for (int i = q, j = n - 1; i--;)
    {
        for (; j >= 0 && a[j][0] > b[i][0]; --j)
        {
            int cn = qry(a[j][1]), r = search(cn), l = search(cn-1);
            ll w = (r-l-1), wl=a[j][1]-l-1, wr =r-a[j][1]-1;
            z += -C2(w) + C2(wl) + C2(wr);
            upd(a[j][1]);
        }
        c[b[i][1]] = z;
    }
    for (int i = 0; i < q; ++i) cout << c[i] << '\n';


    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10584 KB Output is correct
2 Correct 16 ms 10584 KB Output is correct
3 Correct 16 ms 10720 KB Output is correct
4 Correct 16 ms 10588 KB Output is correct
5 Correct 15 ms 10588 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 12628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 8672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -