Submission #896982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896982	2024-01-02T11:50:20 Z	heeheeheehaaw	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1903 ms	102732 KB

sortbooks

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

int v[1000005];
int ri[1000005];
int rez[1000005];
int aintm[4000005];
int aintr[4000005];
vector<int> a;

struct query
{
    int st, dr;
    int k, poz;
};

const int INF = 2e9 + 1;

void buildm(int nod, int st, int dr)
{
    if(st == dr)
    {
        aintm[nod] = v[st];
        return;
    }

    int mij = (st + dr) / 2;
    buildm(nod * 2, st, mij);
    buildm(nod * 2 + 1, mij + 1, dr);
    aintm[nod] = min(aintm[nod * 2], aintm[nod * 2 + 1]);
}

int querym(int nod, int st, int dr, int le, int ri)
{
    if(le > ri) return INF;
    if(st == le && dr == ri)
        return aintm[nod];
    int mij = (st + dr) / 2;
    return min(querym(nod * 2, st, mij, le, min(ri, mij)),
               querym(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}

void buildr(int nod, int st, int dr)
{
    if(st == dr)
    {
        aintr[nod] = INF;
        return;
    }

    int mij = (st + dr) / 2;
    buildr(nod * 2, st, mij);
    buildr(nod * 2 + 1, mij + 1, dr);
    aintr[nod] = INF;
}

void updater(int nod, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        aintr[nod] = val;
        return;
    }

    int mij = (st + dr) / 2;
    if(poz <= mij) updater(nod * 2, st, mij, poz, val);
    else updater(nod * 2 + 1, mij + 1, dr, poz, val);
    aintr[nod] = min(aintr[nod * 2], aintr[nod * 2 + 1]);
}

int queryr(int nod, int st, int dr, int le, int ri)
{
    if(le > ri) return INF;
    if(st == le && dr == ri)
        return aintr[nod];
    int mij = (st + dr) / 2;
    return min(queryr(nod * 2, st, mij, le, min(ri, mij)),
               queryr(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}

bool cmp(query a, query b)
{
    return a.k > b.k;
}

bool cmp2(int a, int b)
{
    return v[a] > v[b];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    stack<int> s;
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>v[i];

    for(int i = n; i >= 1; i--)
    {
        while(!s.empty() && v[i] <= v[s.top()])
            s.pop();
        if(s.empty()) ri[i] = n + 1;
        else ri[i] = s.top();
        s.push(i);
        a.push_back(i);
    }

    buildm(1, 1, n);
    buildr(1, 1, n);

    vector<query> q;
    for(int i = 1; i <= m; i++)
    {
        int st, dr, k, poz = i;
        cin>>st>>dr>>k;
        k -= querym(1, 1, n, st, dr);
        q.push_back({st, dr, k, poz});
    }

    sort(q.begin(), q.end(), cmp);
    sort(a.begin(), a.end(), cmp2);
    int st = 0;

    for(int i = 0; i < q.size(); i++)
    {
        while(st < n && v[a[st]] > q[i].k)
            updater(1, 1, n, a[st], ri[a[st]]), st++;
        int val = queryr(1, 1, n, q[i].st, q[i].dr);
        if(val > q[i].dr) rez[q[i].poz] = 1;
        else rez[q[i].poz] = 0;
    }

    for(int i = 1; i <= m; i++)
        cout<<rez[i]<<'\n';

    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:131:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i = 0; i < q.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Incorrect	1 ms	8536 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Incorrect	1 ms	8536 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1903 ms	101724 KB	Output is correct
2	Correct	1872 ms	101192 KB	Output is correct
3	Correct	1897 ms	101500 KB	Output is correct
4	Correct	1871 ms	102108 KB	Output is correct
5	Correct	1557 ms	102732 KB	Output is correct