oj.uz

Submission #98165

# Submission time Handle Problem Language Result Execution time Memory
98165 2019-02-21T05:41:29 Z 314rate Cambridge (info1cup18_cambridge) C++14
55 / 100
 2000 ms 15468 KB 
#include <bits/stdc++.h>

using namespace std;

struct RMQ_MAX
{
        vector<vector<int>>ret;
        vector<int>mylog;
        void build(int n,int a[])
        {
                ret.resize(n+1);
                mylog.resize(n+1);
                for(int i=2;i<=n;i++)
                {
                        mylog[i]=1+mylog[i/2];
                }
                for(int i=1;i<=n;i++)
                {
                        ret[i].resize(mylog[n]+1,-(1<<30));
                        ret[i][0]=a[i];
                }
                for(int k=1;(1<<k)<=n;k++)
                {
                        for(int i=1;i+(1<<k)-1<=n;i++)
                        {
                                ret[i][k]=max(ret[i][k-1],ret[i+(1<<(k-1))][k-1]);
                        }
                }
        }
        int gt(int l,int r)
        {
                int k=mylog[r-l+1];
                return max(ret[l][k],ret[r-(1<<k)+1][k]);
        }
};

RMQ_MAX rm;

typedef long long ll;

const int N=(int)1e5+7;

int n,m;
int a[N];
int b[N];
ll ps[N];

ll gt(int l,int r)
{
        return ps[r]-ps[l-1];
}

struct info
{
        int a;
        int b;
};

bool cmp(info x,info y)
{
        return x.b<y.b;
}

int main()
{
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i]>>b[i];
                ps[i]=ps[i-1]+a[i];
        }
        rm.build(n,b);
        while(m--)
        {
                int l,r;
                cin>>l>>r;
                ll tots=gt(l,r);
                int big=rm.gt(l,r);
               /// cout<<":"<<tots<<" , "<<big<<"\n";
                if(tots>=(ll)big)
                {
                        cout<<"0\n";
                        continue;
                }
                vector<info>keks;
                for(int i=l;i<=r;i++)
                {
                        keks.push_back({a[i],b[i]});
                }
                sort(keks.begin(),keks.end(),cmp);
                int tos=0;
                bool ok=1;
                for(auto &it:keks)
                {
                        tos+=it.a;
                        if(tos>=it.b)
                        {
                                ok=0;
                                break;
                        }
                }
                cout<<(int)ok<<"\n";
                ///     cout<<"?\n";
        }
}
/**
4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3
**/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 56 ms 14504 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 10 ms 1696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 171 ms 988 KB Output is correct
4 Correct 296 ms 1656 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 56 ms 14504 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 10 ms 1696 KB Output is correct
6 Correct 171 ms 988 KB Output is correct
7 Correct 296 ms 1656 KB Output is correct
8 Execution timed out 2090 ms 15468 KB Time limit exceeded
9 Halted 0 ms 0 KB -