제출 #1117119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117119		Jovica	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	2774 ms	54816 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
int pogolem[1000000];
int niza[1000000];
int drvo[2500000];

int p;
int update(int l,int r,int poz,int k)
{
    if (p<l || r<p) return drvo[poz];
    if (l==r)
    {
        drvo[poz] = max(drvo[poz],k);
        return drvo[poz];
    }
    int mid = (l+r)/2;
    drvo[poz] = max(update(l,mid,poz*2,k),update(mid+1,r,poz*2+1,k));
    return drvo[poz];
}

int najdi(int l,int r,int poz,int levo,int desno)
{
    if (levo<=l && r<=desno) return drvo[poz];
    if (r<levo || desno<l) return 0;
    int mid = (l+r)/2;
    return max(najdi(l,mid,poz*2,levo,desno),najdi(mid+1,r,poz*2+1,levo,desno));
}

int main()
{
    int n,q;
    cin>>n>>q;
    int ns = 1;
    while (ns<n) ns*=2;

    stack<int> s;
    for (int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        niza[i] = a;

        while(s.size() && niza[s.top()]<=a) s.pop();

        if (s.size()) pogolem[i] = s.top();
        else pogolem[i] = -1;
        s.push(i);
    }

    /*
    cout<<"pogolem: ";
    for (int i=0;i<n;i++)
        cout<<pogolem[i]<<" ";
    cout<<endl;
    */

    vector<tuple<int,int,int> > pras;
    for (int i=0;i<q;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        //a--;
        //b--;
        pras.push_back({b,a,c});
    }
    sort(pras.begin(),pras.end());
    int t = 0;

    for (int i=0;i<n;i++)
    {
        if (pogolem[i]!=-1)
        {
            p = pogolem[i];
            p++;
            update(1,ns,1,niza[i]+niza[p-1]);
        }

        while(t<pras.size() && get<0>(pras[t])-1==i)
        {
            int x = najdi(1,ns,1, get<1>(pras[t]),get<0>(pras[t]));
            if (x<=get<2>(pras[t])) cout<<1<<endl;
            else cout<<0<<endl;
            //cout<<"l = "<<get<1>(pras[t])<<" r = "<<get<0>(pras[t])<< " x = "<<x<<endl;
            t++;

        }
    }

    return 0;
}
/*
5 15
2 7 6 8 1
1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
2 2 2
2 3 2
2 4 2
2 5 2
3 3 3
3 4 3
3 5 3
4 4 4
4 5
4
5 5 5
*/

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

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(t<pras.size() && get<0>(pras[t])-1==i)
      |               ~^~~~~~~~~~~~

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