oj.uz

Submission #145684

# Submission time Handle Problem Language Result Execution time Memory
145684 2019-08-20T18:43:29 Z davitmarg Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 255504 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;
char readchar() {
    char c = getchar();
    while (c <= 33) {
        c = getchar();
    }
    return c;
}
 
 
int readint() {
    char c = getchar();
    while (c <= 33) {
        c = getchar();
    }
    bool sign = false;
    if (c == '-') {
        sign = true;
        c = getchar();
    }
    int t = 0;
    while (c >= '0' && c <= '9') {
        t = (t << 3) + (t << 1) + c - '0';
        c = getchar();
    }
    return (sign ? -t: t);
}



int n,m,a[1000006],wmax;
int ans;
vector<int> g[4*1000006];
int t[4*1000006],mn[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];
        mn[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]);
    mn[v]=min(mn[v*2],mn[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;
}

pair<int,int> get2(int v,int l,int r,int i,int j)
{
    if(i>j)
        return MP(-1,mod);
    if(l==i && r==j)
    {
        ans|=(bool)(mx[v]);
        return MP(t[v],mn[v]);
    }
    int m=(l+r)>>1;
    
    pair<int,int> p1,p2;

    p1=get2(v*2,l,m,i,min(j,m));
    p2=get2(v*2+1,m+1,r,max(m+1,i),j);

    if(j<=m)
        return p1;
    else if(i>=m+1)
        return p2;
    else
    {
        if(p1.first>p2.second)
            ans=1;
        return MP(max(p1.first,p2.first),min(p1.second,p2.second));
    }
    
}

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

    while(m--)
    {
        int l,r,k;  
        ans=0;
       // scanf("%d%d%d",&l,&r,&k);
        l=readint();
        r=readint();
        k=readint();

        if(k>wmax || 1)
        {
            get(1,1,n,l,r,-1);
            printf("%c",'0'+(k>=ans));
        }
        else
        {
            get2(1,1,n,l,r);
            printf("%d",(ans==0));
        }
        putchar(10);
    }

	return 0;
}



/*


5 10
2 1 1 1 2
1 5 0
2 5 0
1 4 0
2 4 0
1 5 3

*/

Compilation message

sortbooks.cpp: In function 'int mergeSerge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)
                 ~^~~~~~~~~
sortbooks.cpp:65:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p<a.size())
           ~^~~~~~~~~
sortbooks.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(q<b.size() && b[q]<a[p])
               ~^~~~~~~~~
sortbooks.cpp:71: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 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 90 ms 94332 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94456 KB Output is correct
7 Correct 90 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 93 ms 94388 KB Output is correct
10 Correct 103 ms 94328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 90 ms 94332 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94456 KB Output is correct
7 Correct 90 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 93 ms 94388 KB Output is correct
10 Correct 103 ms 94328 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 97 ms 95460 KB Output is correct
13 Correct 95 ms 95224 KB Output is correct
14 Correct 98 ms 95256 KB Output is correct
15 Correct 99 ms 95352 KB Output is correct
16 Correct 95 ms 95224 KB Output is correct
17 Correct 94 ms 94972 KB Output is correct
18 Correct 95 ms 95224 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 255504 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 111328 KB Output is correct
2 Correct 308 ms 112660 KB Output is correct
3 Correct 272 ms 112756 KB Output is correct
4 Correct 267 ms 112676 KB Output is correct
5 Correct 261 ms 112784 KB Output is correct
6 Correct 217 ms 112496 KB Output is correct
7 Correct 229 ms 112624 KB Output is correct
8 Correct 249 ms 112368 KB Output is correct
9 Correct 126 ms 95904 KB Output is correct
10 Correct 244 ms 112368 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 90 ms 94332 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94456 KB Output is correct
7 Correct 90 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 93 ms 94388 KB Output is correct
10 Correct 103 ms 94328 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 97 ms 95460 KB Output is correct
13 Correct 95 ms 95224 KB Output is correct
14 Correct 98 ms 95256 KB Output is correct
15 Correct 99 ms 95352 KB Output is correct
16 Correct 95 ms 95224 KB Output is correct
17 Correct 94 ms 94972 KB Output is correct
18 Correct 95 ms 95224 KB Output is correct
19 Correct 712 ms 134464 KB Output is correct
20 Correct 702 ms 134552 KB Output is correct
21 Correct 600 ms 134508 KB Output is correct
22 Correct 602 ms 134380 KB Output is correct
23 Correct 591 ms 134336 KB Output is correct
24 Correct 423 ms 134124 KB Output is correct
25 Correct 425 ms 134252 KB Output is correct
26 Correct 501 ms 134540 KB Output is correct
27 Correct 500 ms 134508 KB Output is correct
28 Correct 530 ms 134396 KB Output is correct
29 Correct 518 ms 134536 KB Output is correct
30 Correct 527 ms 134464 KB Output is correct
31 Correct 570 ms 134368 KB Output is correct
32 Correct 549 ms 134512 KB Output is correct
33 Correct 523 ms 134592 KB Output is correct
34 Correct 400 ms 134248 KB Output is correct
35 Correct 392 ms 134124 KB Output is correct
36 Correct 386 ms 133868 KB Output is correct
37 Correct 393 ms 134032 KB Output is correct
38 Correct 392 ms 134224 KB Output is correct
39 Correct 482 ms 132972 KB Output is correct
40 Correct 331 ms 117872 KB Output is correct
41 Correct 467 ms 132692 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94456 KB Output is correct
2 Correct 90 ms 94328 KB Output is correct
3 Correct 90 ms 94332 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94456 KB Output is correct
7 Correct 90 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 93 ms 94388 KB Output is correct
10 Correct 103 ms 94328 KB Output is correct
11 Correct 93 ms 94584 KB Output is correct
12 Correct 97 ms 95460 KB Output is correct
13 Correct 95 ms 95224 KB Output is correct
14 Correct 98 ms 95256 KB Output is correct
15 Correct 99 ms 95352 KB Output is correct
16 Correct 95 ms 95224 KB Output is correct
17 Correct 94 ms 94972 KB Output is correct
18 Correct 95 ms 95224 KB Output is correct
19 Execution timed out 3044 ms 255504 KB Time limit exceeded
20 Halted 0 ms 0 KB -