Submission #494107

#	Time	Username	Problem	Language	Result	Execution time	Memory
494107		stefantaga	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3088 ms	74012 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
int n,m,v[1000005],st[1000005],dr[1000005],cost[1000005];
vector <int> ev[1000005];
int maxim[1000005],i,val[1000005],j,sol[1000005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        val[i]=-v[i];
    }
    for (i=1;i<=m;i++)
    {
        cin>>st[i]>>dr[i]>>cost[i];
        ev[dr[i]].push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        maxim[i]=0;
        for (j=i-1;j>=1;j--)
        {
            if (v[i]<v[j]&&val[j]<v[i])
            {
                val[j]=v[i];
            }
            maxim[j]=max(maxim[j+1],val[j]+v[j]);
        }
        for (j=0;j<ev[i].size();j++)
        {
            if (maxim[st[ev[i][j]]]<=cost[ev[i][j]])
            {
                sol[ev[i][j]]=1;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        cout<<sol[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

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

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