oj.uz

Submission #145556

# Submission time Handle Problem Language Result Execution time Memory
145556 2019-08-20T11:42:53 Z davitmarg Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 262144 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

void myscan(int& res)
{
    int sp=' ';
    int ln=10;
    int zr='0';
    int x;
    res=0;
    while(1)
    {
        x=getchar();
        if(x<zr || x>(zr+9))
            continue;
        res+=x-zr;
        break;
    }
    while(1)
    {
        x=getchar();
        if(x<zr || x>(zr+9))
            break;
        res=res*10+x-zr;
    }
    //cout<<"!!"<<res<<endl;
}

int n,m,a[1000006];
int ans;
vector<int> g[4*1000006];
int t[4*1000006],mx[4*1000006];

int mergeSerge(vector<int>& a,vector<int>& b,vector<int> &c)
{
    int p=0,q=0,d=0;
    for(int i=0;i<b.size();i++)
        if(b[i]<a.back())
            d=a.back()+b[i];
    while(p<a.size())
    {
        while(q<b.size() && b[q]<a[p])
            c.PB(b[q++]);
        c.PB(a[p++]);
    }
    while(q<b.size())
        c.PB(b[q++]);

    return d;
}

void build(int v,int l,int r)
{
    if(l==r)
    {
        t[v]=a[l];
        g[v].PB(a[l]);
        return;
    }
    int m=(l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    mx[v]=mergeSerge(g[v*2],g[v*2+1],g[v]);
    mx[v]=max(mx[v],max(mx[v*2],mx[v*2+1]));
    t[v]=max(t[v*2],t[v*2+1]);
}

int get(int v,int l,int r,int i,int j,int lmax)
{
    if(i>j)
        return -1;
    if(l==i && r==j)
    {
        //cout<<"["<<l<<":"<<r<<"]"<<" "<<lmax<<endl;
        if(g[v][0]<lmax)
            ans=max(ans,lmax+(*(lower_bound(all(g[v]),lmax)-1)));
        ans=max(ans,mx[v]);
        return t[v];
    }
    int m=(l+r)>>1;
    
    int p1,p2;

    p1=get(v*2,l,m,i,min(j,m),lmax);
    lmax=max(lmax,p1);

    p2=get(v*2+1,m+1,r,max(m+1,i),j,lmax);
    lmax=max(lmax,p2);

    return lmax;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        myscan(a[i]);
    build(1,1,n);

    while(m--)
    {
        int l,r,k;  
        ans=0;
       // scanf("%d%d%d",&l,&r,&k);
        myscan(l);
        myscan(r);
        myscan(k);
        get(1,1,n,l,r,-1);
        //cout<<ans<<endl;


        printf("%d\n",(k>=ans));
    }

	return 0;
}
 
/*

3 2 
5 4 4 
1 3 9 
1 3 8 


*/

Compilation message

sortbooks.cpp: In function 'void myscan(int&)':
sortbooks.cpp:28:9: warning: unused variable 'sp' [-Wunused-variable]
     int sp=' ';
         ^~
sortbooks.cpp:29:9: warning: unused variable 'ln' [-Wunused-variable]
     int ln=10;
         ^~
sortbooks.cpp: In function 'int mergeSerge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)
                 ~^~~~~~~~~
sortbooks.cpp:62:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p<a.size())
           ~^~~~~~~~~
sortbooks.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(q<b.size() && b[q]<a[p])
               ~^~~~~~~~~
sortbooks.cpp:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(q<b.size())
           ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 88 ms 94308 KB Output is correct
3 Correct 103 ms 94312 KB Output is correct
4 Correct 91 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94300 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 92 ms 94456 KB Output is correct
9 Correct 89 ms 94372 KB Output is correct
10 Correct 89 ms 94300 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 88 ms 94308 KB Output is correct
3 Correct 103 ms 94312 KB Output is correct
4 Correct 91 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94300 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 92 ms 94456 KB Output is correct
9 Correct 89 ms 94372 KB Output is correct
10 Correct 89 ms 94300 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 96 ms 95068 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 99 ms 95272 KB Output is correct
15 Correct 98 ms 95228 KB Output is correct
16 Correct 95 ms 95096 KB Output is correct
17 Correct 105 ms 94896 KB Output is correct
18 Correct 95 ms 95096 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 111728 KB Output is correct
2 Correct 330 ms 111616 KB Output is correct
3 Correct 277 ms 111652 KB Output is correct
4 Correct 275 ms 111600 KB Output is correct
5 Correct 291 ms 111856 KB Output is correct
6 Correct 253 ms 111472 KB Output is correct
7 Correct 222 ms 111472 KB Output is correct
8 Correct 271 ms 111216 KB Output is correct
9 Correct 131 ms 95864 KB Output is correct
10 Correct 255 ms 111216 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 88 ms 94308 KB Output is correct
3 Correct 103 ms 94312 KB Output is correct
4 Correct 91 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94300 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 92 ms 94456 KB Output is correct
9 Correct 89 ms 94372 KB Output is correct
10 Correct 89 ms 94300 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 96 ms 95068 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 99 ms 95272 KB Output is correct
15 Correct 98 ms 95228 KB Output is correct
16 Correct 95 ms 95096 KB Output is correct
17 Correct 105 ms 94896 KB Output is correct
18 Correct 95 ms 95096 KB Output is correct
19 Correct 723 ms 132420 KB Output is correct
20 Correct 699 ms 132668 KB Output is correct
21 Correct 618 ms 132340 KB Output is correct
22 Correct 600 ms 132388 KB Output is correct
23 Correct 604 ms 132288 KB Output is correct
24 Correct 446 ms 132264 KB Output is correct
25 Correct 436 ms 132076 KB Output is correct
26 Correct 513 ms 132412 KB Output is correct
27 Correct 513 ms 132332 KB Output is correct
28 Correct 523 ms 132460 KB Output is correct
29 Correct 537 ms 132520 KB Output is correct
30 Correct 532 ms 132524 KB Output is correct
31 Correct 533 ms 132552 KB Output is correct
32 Correct 533 ms 132524 KB Output is correct
33 Correct 544 ms 132464 KB Output is correct
34 Correct 407 ms 132204 KB Output is correct
35 Correct 408 ms 132120 KB Output is correct
36 Correct 442 ms 132048 KB Output is correct
37 Correct 399 ms 131836 KB Output is correct
38 Correct 415 ms 132076 KB Output is correct
39 Correct 488 ms 130932 KB Output is correct
40 Correct 346 ms 116824 KB Output is correct
41 Correct 492 ms 130556 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 88 ms 94308 KB Output is correct
3 Correct 103 ms 94312 KB Output is correct
4 Correct 91 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94300 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 92 ms 94456 KB Output is correct
9 Correct 89 ms 94372 KB Output is correct
10 Correct 89 ms 94300 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 96 ms 95068 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 99 ms 95272 KB Output is correct
15 Correct 98 ms 95228 KB Output is correct
16 Correct 95 ms 95096 KB Output is correct
17 Correct 105 ms 94896 KB Output is correct
18 Correct 95 ms 95096 KB Output is correct
19 Execution timed out 3042 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -