oj.uz

Submission #145593

# Submission time Handle Problem Language Result Execution time Memory
145593 2019-08-20T13:22:21 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 &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    while(c==10)
		c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}





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("%c\n",(k>=ans)+'0');
    }

	return 0;
}



/*

3 2 
5 4 4 
1 3 9 
1 3 8 


*/

Compilation message

sortbooks.cpp: In function 'void myscan(int&)':
sortbooks.cpp:30:18: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
     register int c;
                  ^
sortbooks.cpp: In function 'int mergeSerge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)
                 ~^~~~~~~~~
sortbooks.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p<a.size())
           ~^~~~~~~~~
sortbooks.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(q<b.size() && b[q]<a[p])
               ~^~~~~~~~~
sortbooks.cpp:79: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 86 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 91 ms 94328 KB Output is correct
4 Correct 90 ms 94200 KB Output is correct
5 Correct 92 ms 94276 KB Output is correct
6 Correct 90 ms 94200 KB Output is correct
7 Correct 91 ms 94292 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94456 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 91 ms 94328 KB Output is correct
4 Correct 90 ms 94200 KB Output is correct
5 Correct 92 ms 94276 KB Output is correct
6 Correct 90 ms 94200 KB Output is correct
7 Correct 91 ms 94292 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94456 KB Output is correct
11 Correct 93 ms 94480 KB Output is correct
12 Correct 97 ms 95096 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 113 ms 95232 KB Output is correct
15 Correct 102 ms 95160 KB Output is correct
16 Correct 97 ms 95208 KB Output is correct
17 Correct 96 ms 95000 KB Output is correct
18 Correct 96 ms 95152 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 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 330 ms 111584 KB Output is correct
2 Correct 312 ms 111600 KB Output is correct
3 Correct 270 ms 111640 KB Output is correct
4 Correct 263 ms 111608 KB Output is correct
5 Correct 260 ms 111640 KB Output is correct
6 Correct 226 ms 111564 KB Output is correct
7 Correct 218 ms 111476 KB Output is correct
8 Correct 251 ms 111240 KB Output is correct
9 Correct 126 ms 95864 KB Output is correct
10 Correct 246 ms 111216 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 91 ms 94328 KB Output is correct
4 Correct 90 ms 94200 KB Output is correct
5 Correct 92 ms 94276 KB Output is correct
6 Correct 90 ms 94200 KB Output is correct
7 Correct 91 ms 94292 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94456 KB Output is correct
11 Correct 93 ms 94480 KB Output is correct
12 Correct 97 ms 95096 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 113 ms 95232 KB Output is correct
15 Correct 102 ms 95160 KB Output is correct
16 Correct 97 ms 95208 KB Output is correct
17 Correct 96 ms 95000 KB Output is correct
18 Correct 96 ms 95152 KB Output is correct
19 Correct 725 ms 132352 KB Output is correct
20 Correct 705 ms 132460 KB Output is correct
21 Correct 602 ms 132316 KB Output is correct
22 Correct 608 ms 132208 KB Output is correct
23 Correct 633 ms 132376 KB Output is correct
24 Correct 422 ms 132248 KB Output is correct
25 Correct 410 ms 132152 KB Output is correct
26 Correct 527 ms 132264 KB Output is correct
27 Correct 496 ms 132428 KB Output is correct
28 Correct 537 ms 132456 KB Output is correct
29 Correct 543 ms 132412 KB Output is correct
30 Correct 517 ms 132460 KB Output is correct
31 Correct 520 ms 132516 KB Output is correct
32 Correct 524 ms 132492 KB Output is correct
33 Correct 512 ms 132412 KB Output is correct
34 Correct 432 ms 132076 KB Output is correct
35 Correct 393 ms 132048 KB Output is correct
36 Correct 391 ms 131784 KB Output is correct
37 Correct 387 ms 131948 KB Output is correct
38 Correct 398 ms 132024 KB Output is correct
39 Correct 477 ms 131116 KB Output is correct
40 Correct 340 ms 117088 KB Output is correct
41 Correct 458 ms 130668 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 91 ms 94328 KB Output is correct
4 Correct 90 ms 94200 KB Output is correct
5 Correct 92 ms 94276 KB Output is correct
6 Correct 90 ms 94200 KB Output is correct
7 Correct 91 ms 94292 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94456 KB Output is correct
11 Correct 93 ms 94480 KB Output is correct
12 Correct 97 ms 95096 KB Output is correct
13 Correct 96 ms 95096 KB Output is correct
14 Correct 113 ms 95232 KB Output is correct
15 Correct 102 ms 95160 KB Output is correct
16 Correct 97 ms 95208 KB Output is correct
17 Correct 96 ms 95000 KB Output is correct
18 Correct 96 ms 95152 KB Output is correct
19 Execution timed out 3048 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -