oj.uz

답안 #1094290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094290 2024-09-29T09:16:41 Z cpptowin Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 187376 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
const int MAXN = 8000005; // n*(log(max(ai))+4)
namespace WaveletTree
{
    // nenso -> build -> query
    int n;
    int arr[maxn], w[MAXN], nxt = 1, in = 0;
    int lc[MAXN], rc[MAXN], l[MAXN], r[MAXN];
    int b[MAXN];
    const int from = 0, to = maxn;
    vi nen;
    void nenso()
    {
        fo(i, 1, n) nen.pb(arr[i]);
        sort(all(nen));
        nen.erase(unique(all(nen)), nen.end());
        fo(i, 1, n) arr[i] = lower_bound(all(nen), arr[i]) - nen.begin();
    }
    void build(int psz = -1, bool f = 1, int pnd = -1, int nd = 1, int s = from, int e = to)
    {
        l[nd] = ++in, r[nd] = in - 1;
        int midp = psz >> 1, mid = (s + e) >> 1, i1 = (nd == 1) ? n : r[pnd];
        for (int i = (nd == 1) ? 1 : l[pnd]; i <= i1; i++)
            if (nd == 1 || (f && w[i] <= midp) || (!f && w[i] > midp))
                w[in] = (nd == 1) ? arr[i] : w[i], r[nd] = in,
                b[in] = b[in - 1] + (w[in] <= mid), in++;
        if (s == e)
            return;
        int sz = (nd == 1) ? n : r[nd] - l[nd] + 1;
        if (b[r[nd]] - b[l[nd] - 1])
            lc[nd] = ++nxt, build(s + e, 1, nd, lc[nd], s, mid);
        if (b[r[nd]] - b[l[nd] - 1] != sz)
            rc[nd] = ++nxt, build(s + e, 0, nd, rc[nd], mid + 1, e);
    }

    /*
    note:
    - w stores the array elements of each node
    - b stores the prefix sum of frequency of elements <= mid of each node
    - lc contains the node number of the left child of a node
    - rc contains the node number of the right child of a node
    - nxt is used to find the new node number to assign to a node
    - in is used to allot space in the w array for each node
    - [l[nd],r[nd]] is the range for elements of node nd in w and b
    - psz is the number of elements in the parent of a node
    - pnd is the parent of a node
    - f is 1 if the current node is a left child, 0 otherwise
    */

    // kth smallest element in range [l1,r1]
    int kth(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
    {
        if (s == e)
            return s;
        int mid = (s + e) >> 1;
        int got = b[l[nd] + r1] - b[l[nd] + l1 - 1];
        if (got >= k)
            return kth(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid);
        return kth(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k - got, rc[nd], mid + 1, e);
    }

    int KTH(int l, int r, int k)
    {
        return nen[kth(l, r, k)];
    }
    // count of k in range [l1,r1]
    int count(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
    {
        if (s == e)
            return b[l[nd] + r1] - b[l[nd] + l1 - 1];
        int mid = (s + e) >> 1;
        if (mid >= k)
            return count(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid);
        return count(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e);
    }

    int COUNT(int l, int r, int k)
    {
        k = lower_bound(all(nen), k) - nen.begin() + 1;
        return count(l, r, k);
    }
    // count of numbers <= to k in range [l1,r1]
    int lte(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
    {
        if (l1 > r1 || k < s)
            return 0;
        if (e <= k)
            return r1 - l1 + 1;
        int mid = (s + e) >> 1;
        return lte(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid) + lte(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e);
    }
    int LTE(int l, int r, int k)
    {
        k = upper_bound(all(nen), k) - nen.begin() - 1;
        return lte(l, r, k);
    }
}
struct BIT
{
    int t[maxn];
    BIT()
    {
        fo(i, 0, maxn - 1) t[i] = -1;
    }
    void up(int x, int val)
    {
        for (; x < maxn; x += lb(x))
            maximize(t[x], val);
    }
    void clear(int x)
    {
        for (; x < maxn; x += lb(x))
            t[x] = -1;
    }
    int get(int x)
    {
        int ans = -1;
        for (; x; x -= lb(x))
            maximize(ans, t[x]);
        return ans;
    }
} minn;
struct BIT1
{
    int t[maxn];
    BIT1()
    {
        fo(i, 1, maxn - 1) t[i] = -1;
    }
    void up(int x, int val)
    {
        for (; x; x -= lb(x))
            maximize(t[x], val);
    }
    void clear(int x)
    {
        for (; x; x -= lb(x))
            t[x] = -1;
    }
    int get(int x)
    {
        int ans = -1;
        for (; x < maxn; x += lb(x))
            maximize(ans, t[x]);
        return ans;
    }
} maxx;
int n, q, a[maxn];
int res[maxn];
int sum[maxn];
int maxl[maxn];
vi nen;
void calc(int l, int r, vector<array<int, 4>> qry)
{
    int mid = l + r >> 1;
    maxl[mid] = a[mid];
    fod(i, mid - 1, l)
    {
        maxl[i] = max(maxl[i + 1], a[i]);
        int lb = lower_bound(all(nen), a[i + 1]) - nen.begin() + 1;
        minn.up(lb, a[i + 1]);
        lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
        if (minn.get(lb - 1) != -1)
            sum[i] = minn.get(lb - 1) + a[i];
        maximize(sum[i], sum[i + 1]);
    }
    fo(i, mid + 2, r)
    {
        int lb = lower_bound(all(nen), a[i - 1]) - nen.begin() + 1;
        maxx.up(lb, a[i - 1]);
        lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
        if (maxx.get(lb + 1) != -1)
            sum[i] = maxx.get(lb + 1) + a[i];
        maximize(sum[i], sum[i - 1]);
    }
    fod(i, mid, l)
    {
        int lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
        minn.clear(lb);
    }
    fo(i, mid + 1, r)
    {
        int lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
        maxx.clear(lb);
    }
    vector<array<int, 4>> ll, rr;
    for (auto [l, r, val, id] : qry)
        if (l != r)
        {
            if (l <= mid and r >= mid)
            {
                if (max(sum[l], sum[r]) > val)
                    res[id] = 1;
                else
                {
                    int L = max(val - maxl[l], 0);
                    if (WaveletTree::LTE(mid, r - 1, maxl[l] - 1) -
                            WaveletTree::LTE(mid, r - 1, L) >
                        0)
                        res[id] = 1;
                }
            }
            else if (r < mid)
                ll.push_back({l, r, val, id});
            else if (l > mid)
                rr.push_back({l, r, val, id});
        }
    fo(i,l,r) sum[i] = maxl[i] = 0;
    if (l != r)
    {
        calc(l, mid, ll);
        calc(mid + 1, r, rr);
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    WaveletTree::n = n;
    fo(i, 1, n)
    {
        cin >> a[i];
        nen.pb(a[i]);
        WaveletTree::arr[i] = a[i];
    }
    sort(all(nen));
    nen.erase(unique(all(nen)), nen.end());
    // fo(i,1,n) 
    // {
    //     int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1;
    //     cout << lb << ' ';
    // }
    WaveletTree::nenso();
    WaveletTree::build();
    vector<array<int, 4>> qry(q);
    fo(i, 0, q - 1)
    {
        cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
        qry[i][3] = i + 1;
    }
    calc(1, n, qry);
    fo(i, 1, q) cout << (res[i] ^ 1) << "\n";
}

Compilation message

sortbooks.cpp: In function 'void calc(int, int, std::vector<std::array<int, 4> >)':
sortbooks.cpp:210:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  210 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:270:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  270 | main()
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:275:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:276:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  276 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8140 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 5 ms 8516 KB Output is correct
9 Correct 4 ms 8296 KB Output is correct
10 Correct 5 ms 8280 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8140 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 5 ms 8516 KB Output is correct
9 Correct 4 ms 8296 KB Output is correct
10 Correct 5 ms 8280 KB Output is correct
11 Correct 7 ms 8796 KB Output is correct
12 Correct 17 ms 9776 KB Output is correct
13 Correct 17 ms 9564 KB Output is correct
14 Correct 19 ms 9980 KB Output is correct
15 Correct 23 ms 9816 KB Output is correct
16 Correct 16 ms 9820 KB Output is correct
17 Correct 13 ms 9564 KB Output is correct
18 Correct 9 ms 9564 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 187376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 36176 KB Output is correct
2 Correct 345 ms 32640 KB Output is correct
3 Correct 157 ms 33624 KB Output is correct
4 Correct 162 ms 34644 KB Output is correct
5 Correct 185 ms 35920 KB Output is correct
6 Correct 155 ms 32856 KB Output is correct
7 Correct 182 ms 32440 KB Output is correct
8 Correct 129 ms 33672 KB Output is correct
9 Correct 41 ms 15064 KB Output is correct
10 Correct 130 ms 33624 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8140 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 5 ms 8516 KB Output is correct
9 Correct 4 ms 8296 KB Output is correct
10 Correct 5 ms 8280 KB Output is correct
11 Correct 7 ms 8796 KB Output is correct
12 Correct 17 ms 9776 KB Output is correct
13 Correct 17 ms 9564 KB Output is correct
14 Correct 19 ms 9980 KB Output is correct
15 Correct 23 ms 9816 KB Output is correct
16 Correct 16 ms 9820 KB Output is correct
17 Correct 13 ms 9564 KB Output is correct
18 Correct 9 ms 9564 KB Output is correct
19 Correct 1284 ms 76268 KB Output is correct
20 Correct 1256 ms 76100 KB Output is correct
21 Correct 1273 ms 68804 KB Output is correct
22 Correct 1227 ms 68684 KB Output is correct
23 Correct 1266 ms 69196 KB Output is correct
24 Correct 625 ms 68172 KB Output is correct
25 Correct 623 ms 67916 KB Output is correct
26 Correct 634 ms 68184 KB Output is correct
27 Correct 648 ms 68076 KB Output is correct
28 Correct 661 ms 68172 KB Output is correct
29 Correct 644 ms 75596 KB Output is correct
30 Correct 649 ms 75516 KB Output is correct
31 Correct 679 ms 74076 KB Output is correct
32 Correct 694 ms 73996 KB Output is correct
33 Correct 622 ms 74056 KB Output is correct
34 Correct 585 ms 68432 KB Output is correct
35 Correct 599 ms 68680 KB Output is correct
36 Correct 631 ms 68432 KB Output is correct
37 Correct 617 ms 68428 KB Output is correct
38 Correct 615 ms 68496 KB Output is correct
39 Correct 759 ms 69340 KB Output is correct
40 Correct 435 ms 54088 KB Output is correct
41 Correct 272 ms 60224 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8140 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 5 ms 8516 KB Output is correct
9 Correct 4 ms 8296 KB Output is correct
10 Correct 5 ms 8280 KB Output is correct
11 Correct 7 ms 8796 KB Output is correct
12 Correct 17 ms 9776 KB Output is correct
13 Correct 17 ms 9564 KB Output is correct
14 Correct 19 ms 9980 KB Output is correct
15 Correct 23 ms 9816 KB Output is correct
16 Correct 16 ms 9820 KB Output is correct
17 Correct 13 ms 9564 KB Output is correct
18 Correct 9 ms 9564 KB Output is correct
19 Execution timed out 3056 ms 187376 KB Time limit exceeded
20 Halted 0 ms 0 KB -