Submission #1040465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040465		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	816 ms	67672 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];
struct dl
{
    int vt;
    int gt;
    int id;
};
vector<dl> tv[1000009];

int s[1000009], top;

int st[4000009];

void update(int vt, int gt, int goc = 1, int l = 1, int r = n)
{
    if (vt < l || vt > r) return;
    if (l == r)
    {
        st[goc] = gt;
        return;
    }
    int mid = (l+r)/2;
    update(vt,gt,goc*2,l,mid);
    update(vt,gt,goc*2+1,mid+1,r);
    st[goc] = max(st[goc*2], st[goc*2+1]);
}

int get(int d, int c, int goc = 1, int l = 1, int r = n)
{
    if (c < l || d > r) return -1;
    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));
}

bool kq[1000009];

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)
    {
        int l, r, gt;
        cin >> l >> r >> gt;
        tv[r].pb({l,gt,i});
    }
    fi(i,1,n)
    {
        while(top > 0 && a[s[top]] <= a[i]) top--;
        update(s[top], a[s[top]] + a[i]);
        s[++top] = i;
        for(dl tg: tv[i])
        {
            int vt = tg.vt, gt = tg.gt, id = tg.id;
            //cout << id  << " " << get(vt, i) << endl;
            kq[id] = (get(vt, i) <= gt);
        }
    }
    fi(i,1,q) cout << kq[i] << endl;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(HTManh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(HTManh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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