Submission #1040406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040406		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3056 ms	204800 KiB

sortbooks

#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;

int n, q;
ll a[1000009];
pair<pair<pii, ll>, int> tv[1000009];

ll st[4000009];
ll mx[4000009];
pll lazy[4000009];
ll luoi[4000009];

bool kq[1000009];

vector<int> query[1000009][2];

void build(int goc = 1, int l = 1, int r = q)
{
    lazy[goc] = {-1, 0};
    luoi[goc] = -1;
    if (l == r)
    {
        st[goc] = -1e9;
        mx[goc] = -1e9;
        return;
    }
    int mid = (l+r)/2;
    build(goc*2,l,mid);
    build(goc*2+1,mid+1,r);
    st[goc] = max(st[goc*2], st[goc*2+1]);
}

void down(int goc, int l, int r)
{
    st[goc] = max(st[goc], lazy[goc].st);
    st[goc] += lazy[goc].nd;
    mx[goc] = max(mx[goc], st[goc]);
    if (l != r)
    {
        lazy[goc*2].st = max(lazy[goc*2].st, lazy[goc].st - lazy[goc*2].nd);
        lazy[goc*2].nd += lazy[goc].nd;

        lazy[goc*2+1].st = max(lazy[goc*2+1].st, lazy[goc].st - lazy[goc*2+1].nd);
        lazy[goc*2+1].nd += lazy[goc].nd;
    }
    lazy[goc] = {-1, 0};
}

void update1(int d, int c, int gt, int goc = 1, int l = 1, int r = q)
{
    down(goc,l,r);
    if (c < l || d > r) return;
    if (d <= l && r <= c)
    {
        lazy[goc].st = gt;
        down(goc,l,r);
        return;
    }
    int mid = (l+r)/2;
    update1(d,c,gt,goc*2,l,mid);
    update1(d,c,gt,goc*2+1,mid+1,r);
    st[goc] = max(st[goc*2], st[goc*2+1]);
}

void update2(int d, int c, int gt, int goc = 1, int l = 1, int r = q)
{
    down(goc,l,r);
    if (c < l || d > r) return;
    if (d <= l && r <= c)
    {
        lazy[goc].nd += gt;
        down(goc,l,r);
        return;
    }
    int mid = (l+r)/2;
    update2(d,c,gt,goc*2,l,mid);
    update2(d,c,gt,goc*2+1,mid+1,r);
    st[goc] = max(st[goc*2], st[goc*2+1]);
}

void xuong(int goc, int l, int r)
{
    mx[goc] = max(mx[goc], luoi[goc]);
    if (l != r)
    {
        luoi[goc*2] = max(luoi[goc*2], luoi[goc]);
        luoi[goc*2+1] = max(luoi[goc*2+1], luoi[goc]);
    }
    luoi[goc] = 0;
}

void capnhat(int d, int c, int goc = 1, int l = 1, int r = q)
{
    xuong(goc,l,r);
    if (c < l || d > r) return;
    if (d <= l && r <= c)
    {
        luoi[goc] = max(luoi[goc], st[goc]);
        xuong(goc,l,r);
        return;
    }
    int mid = (l+r)/2;
    capnhat(d,c,goc*2,l,mid);
    capnhat(d,c,goc*2+1,mid+1,r);
    mx[goc] = max(mx[goc*2], mx[goc*2+1]);
}

ll get(int d, int c, int goc = 1, int l = 1, int r = q)
{
    down(goc,l,r);
    if (c < l || d > r) return -1e9;
    if (d <= l && r <= c) return st[goc];
    int mid = (l+r)/2;
    return max(get(d,c,goc*2,l,mid), get(d,c,goc*2+1,mid+1,r));
}

ll lay(int d, int c, int goc = 1, int l = 1, int r = q)
{
    xuong(goc,l,r);
    if (c < l || d > r) return -1e9;
    if (d <= l && r <= c) return mx[goc];
    int mid = (l+r)/2;
    return max(lay(d,c,goc*2,l,mid), lay(d,c,goc*2+1,mid+1,r));
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	if (fopen(HTManh".inp", "r"))
    {
        freopen(HTManh".inp", "r", stdin);
        freopen(HTManh".out", "w", stdout);
    }

    cin >> n >> q;
    fi(i,1,n) cin >> a[i];
    fi(i,1,q) cin >> tv[i].st.st.st >> tv[i].st.st.nd >> tv[i].st.nd;
    fi(i,1,q) tv[i].nd = i;
    sort(tv+1,tv+q+1);
    fi(i,1,q)
    {
        query[tv[i].st.st.st][0].pb(i);
        query[tv[i].st.st.nd][1].pb(i);
    }

    build();
    int ctro = 0;
    fi(i,1,n)
    {
        for(int x: query[i][0])
        {
            update1(x,x,a[i]);
            ctro = x;
        }
        update1(1,ctro,a[i]);
        int d = 1, c = n;
        while(d <= c)
        {
            int g = (d+c)/2;
            if (get(g,n) <= a[i]) c = g - 1;
            else d = g + 1;
        }
        update2(1,c,a[i]);
        capnhat(1,c);
        update2(1,c,-a[i]);
        for(int x: query[i][0])
        {
            ll gt = lay(x,x);
            if (gt <= tv[i].st.nd) kq[tv[i].nd] = 1;
        }
    }
    fi(i,1,q) cout << kq[i] << endl;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(HTManh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(HTManh".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