제출 #494111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494111		stefantaga	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	929 ms	75124 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 aib[1000005],i,j,sol[1000005];
stack <int> stac;
int ub (int x)
{
    return x&(-x);
}
void update(int poz,int x)
{
    for (int i=poz;i<=n;i+=ub(i))
    {
        aib[i]=max(aib[i],x);
    }
}
int maxi(int poz)
{
    int maxim=0;
    for (int i=poz;i>=1;i-=ub(i))
    {
        maxim=max(aib[i],maxim);
    }
    return maxim;
}
vector <pair <int,int>> ceau;
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];
    }
    for (i=1;i<=m;i++)
    {
        cin>>st[i]>>dr[i]>>cost[i];
        ev[st[i]].push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        while (!stac.empty()&&v[stac.top()]<=v[i])
        {
            stac.pop();
        }
        if (!stac.empty())
        {
            ceau.push_back({stac.top(),i});
        }
        stac.push(i);
    }
    int poz=ceau.size()-1;
    for (i=n;i>=1;i--)
    {
        while (poz>=0&&ceau[poz].first>=i)
        {
            update(ceau[poz].second,v[ceau[poz].first]+v[ceau[poz].second]);
            poz--;
        }
        for (j=0;j<ev[i].size();j++)
        {
            if (maxi(dr[ev[i][j]])<=cost[ev[i][j]])
            {
                sol[ev[i][j]]=1;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        cout<<sol[i]<<'\n';
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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