oj.uz

답안 #1094287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094287 2024-09-29T09:07:57 Z cpptowin Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 351 ms 185280 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());
    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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 273 ms 185280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 35784 KB Output is correct
2 Correct 351 ms 32276 KB Output is correct
3 Correct 189 ms 33232 KB Output is correct
4 Correct 164 ms 34252 KB Output is correct
5 Correct 162 ms 35532 KB Output is correct
6 Correct 166 ms 32208 KB Output is correct
7 Correct 145 ms 32212 KB Output is correct
8 Correct 142 ms 33228 KB Output is correct
9 Correct 40 ms 14924 KB Output is correct
10 Correct 129 ms 33236 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -