Submission #993599

#	Time	Username	Problem	Language	Result	Execution time	Memory
993599		n3rm1n	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	920 ms	115068 KiB

sortbooks

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const long long MAXN = 1e6+10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
long long n, m;
long long a[MAXN];

long long l, r, k;

long long inpair[MAXN];
long long pairw[MAXN];
void read_array()
{
    cin >> n >> m;
    stack < long long > s;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        while(!s.empty() && a[s.top()] <= a[i])
            s.pop();
        if(!s.empty())
        {
            inpair[i] = s.top();
            pairw[i] = a[i] + a[s.top()];
        }
        s.push(i);
    }
   /**cout << "**" << endl;
    for (long long i = 1;i <= n; ++ i)
       cout << inpair[i] << " ";
    cout << endl;
    cout << "**" << endl;
    for (long long i = 1;i <= n; ++ i)
       cout << pairw[i] << " ";
    cout << endl;*/
}
struct que
{
    long long ql, qr, w, id;
    que(){};
    que(long long _ql, long long _qr, long long _w, long long _id)
    {
        ql = _ql;
        qr = _qr;
        w = _w;
        id = _id;
    }
};
vector < que > g;
bool cmp(que q1, que q2)
{
    if(q1.qr != q2.qr)return(q1.qr < q2.qr);
    return (q1.id < q2.id);
}
long long t[MAXN * 4];
long long ql, qr;
long long query(long long i, long long l, long long r)
{
    if(ql <= l && r <= qr)return t[i];
    if(qr < l || ql > r)return 0;
    long long mid = (l + r)/2;
    return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
long long pos, val;
void update(long long i, long long l, long long r)
{
    if(l == r)
    {
        t[i] = max(t[i], val);
        return;
    }
    long long mid = (l + r)/2;
    if(pos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}
long long ans[MAXN];
void queries()
{

    for (long long i = 1; i <= m; ++ i)
    {
        cin >> l >> r >> k;
        g.push_back(que(l, r, k, i));
    }
    sort(g.begin(), g.end(), cmp);
    long long last = 0;
    long long qll, qrr, ww, idd;
    for (long long i = 0; i < g.size(); ++ i)
    {
        qll = g[i].ql;
        qrr = g[i].qr;
        ww = g[i].w;
        idd = g[i].id;
       // cout << qll << " " << qrr << " " << ww << " " << idd << endl;
        for (long long j = last+1; j <= qrr; ++ j)
        {
            if(!inpair[j])continue;
            pos = inpair[j];
            val = pairw[j];
          //  cout << "in " << pos << " " << val << endl;
            update(1, 1, n);
        }

        ql = qll;
        qr = qrr-1;

        long long res = query(1, 1, n);
        // cout << "final res " << res << endl;
        if(res <= ww)ans[idd] = 1;

        last = qrr;
    }
    for (long long i =1; i <= m; ++ i)
    {
        cout << ans[i] << endl;
    }
}
int main()
{
    speed();

    read_array();
    queries();
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void queries()':
sortbooks.cpp:96:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (long long i = 0; i < g.size(); ++ i)
      |                           ~~^~~~~~~~~~

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