oj.uz

Submission #993271

# Submission time Handle Problem Language Result Execution time Memory
993271 2024-06-05T13:16:09 Z vivkostov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 248952 KB 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,q,a[1000005],l,r,c,cost[4000005];
vector<int>p[4000005];
mt19937 mt(time(nullptr));
int merg(vector<int>v1,vector<int>v2,vector<int>&v)
{
    int p1=0,p2=0,cos=0;
    for(int i=1;i<=v1.size()+v2.size();i++)
    {
        if(p1==v1.size())
        {
            v.push_back(v2[p2]);
            p2++;
        }
        else if(p2==v2.size())
        {
            v.push_back(v1[p1]);
            cos=max(v2[p2-1]+v1[p1],cos);
            p1++;
        }
        else if(v1[p1]>v2[p2])
        {
            v.push_back(v2[p2]);
            cos=max(cos,v2[p2]+v1[p1]);
            p2++;
        }
        else
        {
            v.push_back(v1[p1]);
            p1++;
        }
    }
    return cos;
}
void check(int l,int r,int h)
{
    cout<<l<<" "<<r<<" "<<cost[h]<<" | ";
    for(int i=0;i<p[h].size();i++)
    {
        cout<<p[h][i]<<" ";
    }
    cout<<endl;
    if(l==r)return;
    int m=(l+r)/2;
    check(l,m,h*2);
    check(m+1,r,h*2+1);
}
void build_tree(int l,int r,int h)
{
    if(l==r)
    {
        p[h].push_back(a[l]);
        return;
    }
    int m=(l+r)/2;
    build_tree(l,m,h*2);
    build_tree(m+1,r,h*2+1);
    cost[h]=merg(p[h*2],p[h*2+1],p[h]);
    cost[h]=max(max(cost[h*2],cost[h*2+1]),cost[h]);
}
int otg[10005],ot,maotg;
void query(int l,int r,int ql,int qr,int h)
{
    if(r<ql||l>qr)return;
    if(l>=ql&&r<=qr)
    {
        //cout<<l<<" "<<r<<endl;
        ot++;
        otg[ot]=h;
        maotg=max(maotg,cost[h]);
        return;
    }
    int m=(l+r)/2;
    query(l,m,ql,qr,h*2);
    query(m+1,r,ql,qr,h*2+1);
}
void make_otg()
{
    for(int i=1;i<=ot;i++)
    {
        int w=p[otg[i]][p[otg[i]].size()-1];
        for(int j=i+1;j<=ot;j++)
        {
            int l=0,r=p[otg[j]].size()-1,m;
            while(l<=r)
            {
                m=(l+r)/2;
                if(w<=p[otg[j]][m])l=m+1;
                else r=m-1;
            }
            if(l!=0)maotg=max(maotg,w+p[otg[j]][l-1]);
        }
        //cout<<endl;
        otg[i]=0;
    }
    ot=0;
}
void dumb_query(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return;
    if(l==r)
    {
        ot++;
        otg[ot]=h;
        return;
    }
    int m=(l+r)/2;
    dumb_query(l,m,ql,qr,h*2);
    dumb_query(m+1,r,ql,qr,h*2+1);
}
void dumb_make_otg()
{
    for(int i=1;i<=ot;i++)
    {
        int w=p[otg[i]][p[otg[i]].size()-1];
        for(int j=i+1;j<=ot;j++)
        {
            for(int z=p[otg[j]].size()-1;z>=0;z--)
            {
                if(w>p[otg[j]][z])
                {
                    maotg=max(maotg,p[otg[j]][z]+w);
                    break;
                }
            }
        }
        otg[i]=0;
    }
    ot=0;
}
void read()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        //a[i]=mt()%20+1;
        //cout<<a[i]<<" ";
    }
    //cout<<endl;
    build_tree(1,n,1);
    //check(1,n,1);
    for(int i=1;i<=q;i++)
    {
        cin>>l>>r>>c;
        dumb_query(1,n,l,r,1);
        dumb_make_otg();
        //cout<<maotg<<" ";
        if(maotg<=c)cout<<1<<endl;
        else cout<<0<<endl;
        maotg=0;
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int merg(std::vector<int>, std::vector<int>, std::vector<int>&)':
sortbooks.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=1;i<=v1.size()+v2.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(p1==v1.size())
      |            ~~^~~~~~~~~~~
sortbooks.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         else if(p2==v2.size())
      |                 ~~^~~~~~~~~~~
sortbooks.cpp: In function 'void check(int, int, int)':
sortbooks.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<p[h].size();i++)
      |                 ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94288 KB Output is correct
2 Correct 37 ms 94300 KB Output is correct
3 Correct 40 ms 94288 KB Output is correct
4 Correct 39 ms 94296 KB Output is correct
5 Correct 39 ms 94300 KB Output is correct
6 Correct 63 ms 94288 KB Output is correct
7 Correct 66 ms 94300 KB Output is correct
8 Correct 98 ms 94288 KB Output is correct
9 Correct 55 ms 94416 KB Output is correct
10 Correct 94 ms 94456 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94288 KB Output is correct
2 Correct 37 ms 94300 KB Output is correct
3 Correct 40 ms 94288 KB Output is correct
4 Correct 39 ms 94296 KB Output is correct
5 Correct 39 ms 94300 KB Output is correct
6 Correct 63 ms 94288 KB Output is correct
7 Correct 66 ms 94300 KB Output is correct
8 Correct 98 ms 94288 KB Output is correct
9 Correct 55 ms 94416 KB Output is correct
10 Correct 94 ms 94456 KB Output is correct
11 Correct 1327 ms 94652 KB Output is correct
12 Execution timed out 3073 ms 95060 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3110 ms 248952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 109572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94288 KB Output is correct
2 Correct 37 ms 94300 KB Output is correct
3 Correct 40 ms 94288 KB Output is correct
4 Correct 39 ms 94296 KB Output is correct
5 Correct 39 ms 94300 KB Output is correct
6 Correct 63 ms 94288 KB Output is correct
7 Correct 66 ms 94300 KB Output is correct
8 Correct 98 ms 94288 KB Output is correct
9 Correct 55 ms 94416 KB Output is correct
10 Correct 94 ms 94456 KB Output is correct
11 Correct 1327 ms 94652 KB Output is correct
12 Execution timed out 3073 ms 95060 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94288 KB Output is correct
2 Correct 37 ms 94300 KB Output is correct
3 Correct 40 ms 94288 KB Output is correct
4 Correct 39 ms 94296 KB Output is correct
5 Correct 39 ms 94300 KB Output is correct
6 Correct 63 ms 94288 KB Output is correct
7 Correct 66 ms 94300 KB Output is correct
8 Correct 98 ms 94288 KB Output is correct
9 Correct 55 ms 94416 KB Output is correct
10 Correct 94 ms 94456 KB Output is correct
11 Correct 1327 ms 94652 KB Output is correct
12 Execution timed out 3073 ms 95060 KB Time limit exceeded
13 Halted 0 ms 0 KB -