oj.uz

Submission #1094295

# Submission time Handle Problem Language Result Execution time Memory
1094295 2024-09-29T09:22:56 Z cpptowin Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1236 ms 262144 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;
static struct FastInput
{
    static constexpr int BUF_SIZE = 1 << 20;
    char buf[BUF_SIZE];
    size_t chars_read = 0;
    size_t buf_pos = 0;
    FILE *in = stdin;
    char cur = 0;

    inline char get_char()
    {
        if (buf_pos >= chars_read)
        {
            chars_read = fread(buf, 1, BUF_SIZE, in);
            buf_pos = 0;
            buf[0] = (chars_read == 0 ? -1 : buf[0]);
        }
        return cur = buf[buf_pos++];
    }

    inline void tie(int) {}

    inline explicit operator bool()
    {
        return cur != -1;
    }

    inline static bool is_blank(char c)
    {
        return c <= ' ';
    }

    inline bool skip_blanks()
    {
        while (is_blank(cur) && cur != -1)
        {
            get_char();
        }
        return cur != -1;
    }

    inline FastInput &operator>>(char &c)
    {
        skip_blanks();
        c = cur;
        return *this;
    }

    inline FastInput &operator>>(string &s)
    {
        if (skip_blanks())
        {
            s.clear();
            do
            {
                s += cur;
            } while (!is_blank(get_char()));
        }
        return *this;
    }

    template <typename T>
    inline FastInput &read_integer(T &n)
    {
        // unsafe, doesn't check that characters are actually digits
        n = 0;
        if (skip_blanks())
        {
            int sign = +1;
            if (cur == '-')
            {
                sign = -1;
                get_char();
            }
            do
            {
                n += n + (n << 3) + cur - '0';
            } while (!is_blank(get_char()));
            n *= sign;
        }
        return *this;
    }

    template <typename T>
    inline typename enable_if<is_integral<T>::value, FastInput &>::type operator>>(T &n)
    {
        return read_integer(n);
    }

#if !defined(_WIN32) || defined(_WIN64)
    inline FastInput &operator>>(__int128 &n)
    {
        return read_integer(n);
    }
#endif

    template <typename T>
    inline typename enable_if<is_floating_point<T>::value, FastInput &>::type operator>>(T &n)
    {
        // not sure if really fast, for compatibility only
        n = 0;
        if (skip_blanks())
        {
            string s;
            (*this) >> s;
            sscanf(s.c_str(), "%lf", &n);
        }
        return *this;
    }
} fast_input;

#define cin fast_input

static struct FastOutput
{
    static constexpr int BUF_SIZE = 1 << 20;
    char buf[BUF_SIZE];
    size_t buf_pos = 0;
    static constexpr int TMP_SIZE = 1 << 20;
    char tmp[TMP_SIZE];
    FILE *out = stdout;

    inline void put_char(char c)
    {
        buf[buf_pos++] = c;
        if (buf_pos == BUF_SIZE)
        {
            fwrite(buf, 1, buf_pos, out);
            buf_pos = 0;
        }
    }

    ~FastOutput()
    {
        fwrite(buf, 1, buf_pos, out);
    }

    inline FastOutput &operator<<(char c)
    {
        put_char(c);
        return *this;
    }

    inline FastOutput &operator<<(const char *s)
    {
        while (*s)
        {
            put_char(*s++);
        }
        return *this;
    }

    inline FastOutput &operator<<(const string &s)
    {
        for (int i = 0; i < (int)s.size(); i++)
        {
            put_char(s[i]);
        }
        return *this;
    }

    template <typename T>
    inline char *integer_to_string(T n)
    {
        // beware of TMP_SIZE
        char *p = tmp + TMP_SIZE - 1;
        if (n == 0)
        {
            *--p = '0';
        }
        else
        {
            bool is_negative = false;
            if (n < 0)
            {
                is_negative = true;
                n = -n;
            }
            while (n > 0)
            {
                *--p = (char)('0' + n % 10);
                n /= 10;
            }
            if (is_negative)
            {
                *--p = '-';
            }
        }
        return p;
    }

    template <typename T>
    inline typename enable_if<is_integral<T>::value, char *>::type stringify(T n)
    {
        return integer_to_string(n);
    }

#if !defined(_WIN32) || defined(_WIN64)
    inline char *stringify(__int128 n)
    {
        return integer_to_string(n);
    }
#endif

    template <typename T>
    inline typename enable_if<is_floating_point<T>::value, char *>::type stringify(T n)
    {
        sprintf(tmp, "%.17f", n);
        return tmp;
    }

    template <typename T>
    inline FastOutput &operator<<(const T &n)
    {
        auto p = stringify(n);
        for (; *p != 0; p++)
        {
            put_char(*p);
        }
        return *this;
    }
} fast_output;

#define cout fast_output
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 = 50000005; // 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::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:434:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  434 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:494:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  494 | main()
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:503:13: warning: passing NULL to non-pointer argument 1 of 'void FastInput::tie(int)' [-Wconversion-null]
  503 |     cin.tie(NULL);
      |             ^~~~
sortbooks.cpp:61:21: note:   declared here
   61 |     inline void tie(int) {}
      |                     ^~~
sortbooks.cpp:499:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  499 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:500:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  500 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8368 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8368 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 7 ms 9052 KB Output is correct
12 Correct 21 ms 9640 KB Output is correct
13 Correct 19 ms 9820 KB Output is correct
14 Correct 18 ms 10076 KB Output is correct
15 Correct 22 ms 10076 KB Output is correct
16 Correct 18 ms 9816 KB Output is correct
17 Correct 13 ms 9816 KB Output is correct
18 Correct 8 ms 9564 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 691 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 36944 KB Output is correct
2 Correct 338 ms 33344 KB Output is correct
3 Correct 142 ms 34392 KB Output is correct
4 Correct 146 ms 35412 KB Output is correct
5 Correct 145 ms 36776 KB Output is correct
6 Correct 135 ms 33460 KB Output is correct
7 Correct 140 ms 33368 KB Output is correct
8 Correct 121 ms 34640 KB Output is correct
9 Correct 34 ms 15948 KB Output is correct
10 Correct 111 ms 34644 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8368 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 7 ms 9052 KB Output is correct
12 Correct 21 ms 9640 KB Output is correct
13 Correct 19 ms 9820 KB Output is correct
14 Correct 18 ms 10076 KB Output is correct
15 Correct 22 ms 10076 KB Output is correct
16 Correct 18 ms 9816 KB Output is correct
17 Correct 13 ms 9816 KB Output is correct
18 Correct 8 ms 9564 KB Output is correct
19 Correct 1212 ms 76264 KB Output is correct
20 Correct 1236 ms 74124 KB Output is correct
21 Correct 1200 ms 66896 KB Output is correct
22 Correct 1194 ms 67060 KB Output is correct
23 Correct 1195 ms 66904 KB Output is correct
24 Correct 607 ms 66128 KB Output is correct
25 Correct 624 ms 66128 KB Output is correct
26 Correct 586 ms 66376 KB Output is correct
27 Correct 594 ms 66132 KB Output is correct
28 Correct 598 ms 66164 KB Output is correct
29 Correct 600 ms 73804 KB Output is correct
30 Correct 612 ms 71628 KB Output is correct
31 Correct 598 ms 68428 KB Output is correct
32 Correct 598 ms 68464 KB Output is correct
33 Correct 594 ms 68460 KB Output is correct
34 Correct 563 ms 63312 KB Output is correct
35 Correct 559 ms 63308 KB Output is correct
36 Correct 569 ms 63312 KB Output is correct
37 Correct 572 ms 63480 KB Output is correct
38 Correct 576 ms 63348 KB Output is correct
39 Correct 713 ms 65100 KB Output is correct
40 Correct 389 ms 50772 KB Output is correct
41 Correct 233 ms 56656 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8368 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 7 ms 9052 KB Output is correct
12 Correct 21 ms 9640 KB Output is correct
13 Correct 19 ms 9820 KB Output is correct
14 Correct 18 ms 10076 KB Output is correct
15 Correct 22 ms 10076 KB Output is correct
16 Correct 18 ms 9816 KB Output is correct
17 Correct 13 ms 9816 KB Output is correct
18 Correct 8 ms 9564 KB Output is correct
19 Runtime error 691 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -