Submission #1094255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094255		cpptowin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2004 ms	262148 KiB

sortbooks

#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 int long long
#define inf (int)1e18
#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];
    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] = 0;
    }
    int get(int x)
    {
        int ans = 0;
        for( ; x ; x -= lb(x)) maximize(ans,t[x]);
        return ans;
    }
}minn;
struct BIT1
{
    int t[maxn];
    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] = 0;
    }
    int get(int x)
    {
        int ans = 0;
        for( ; x < maxn ; x += lb(x)) maximize(ans,t[x]);
        return ans;
    }
}maxx;
int n,q,a[maxn];
int res[maxn];
int suml[maxn],sumr[maxn];
int maxl[maxn];
vi nen;
void calc(int l,int r,vector<array<int,4>> qry)
{
    int mid = l + r >> 1;
    fod(i,mid,l) 
    {
        maxl[i] = max(maxl[i + 1],a[i]);
        int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1;
        suml[i] = minn.get(lb) + a[i];
        maximize(suml[i],suml[i + 1]);
        minn.up(lb,a[i]);
    }
    fo(i,mid + 1,r)
    {
        int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1;
        sumr[i] = maxx.get(lb) + a[i];
        maximize(sumr[i],sumr[i - 1]);
        maxx.up(lb,a[i]);
    }
    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 <= mid and r >= mid)
        {
            if(max(suml[l],sumr[r]) > val) res[id] = 1;
            else 
            {
                int L = max(val - maxl[l],0ll);
                if(WaveletTree::lte(mid,r - 1,maxl[l]) - 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});
    }
    fod(i,mid,l) 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);
    // cout << WaveletTree::lte(0,4,8);en;
    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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23