oj.uz

Submission #709787

# Submission time Handle Problem Language Result Execution time Memory
709787 2023-03-14T12:22:45 Z groshi Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 185224 KB 
#include<iostream>
#include<vector>
using namespace std;
const int T = 1<<20;
vector<vector<int> > drzewo;
int wynik[2*T];
int maxx=0;
int wynikk=0;
int pot=1;
void dodaj(int x)
{
    wynikk=max(wynikk,wynik[x]);
    if(drzewo[x].size()==0)
        return;
    int mam=drzewo[x].back();
    int gdzie=lower_bound(drzewo[x].begin(),drzewo[x].end(),maxx)-drzewo[x].begin();
    if(gdzie>=1)
        wynikk=max(wynikk,maxx+drzewo[x][gdzie-1]);
    maxx=max(maxx,mam);
}
void zapp(int x,int l,int r,int a,int b)
{
    if(l>b || r<a)
        return;
    if(a<=l && r<=b)
    {
        dodaj(x);
        return;
    }
    int mid=(l+r)/2;
    zapp(x*2,l,mid,a,b);
    zapp(x*2+1,mid+1,r,a,b);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,zap,x;
    cin>>n>>zap;
    while(pot<=n)
        pot*=2;
    pot--;
    drzewo.resize(2*pot+2);
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        drzewo[i+pot].push_back(x);
    }
    for(int i=pot;i>=1;i--)
    {
        ///merguje i*2 z i*2+1
        wynik[i]=max(wynik[i*2],wynik[i*2+1]);
        if(drzewo[i*2].size()>0)
        {
            int jest=drzewo[i*2].back();
            int gdzie=lower_bound(drzewo[i*2+1].begin(),drzewo[i*2+1].end(),jest)-drzewo[i*2+1].begin();
            if(gdzie>=1)
                wynik[i]=max(wynik[i],jest+drzewo[i*2+1][gdzie-1]);
        }
        int l=0,r=0;
        while(l<drzewo[i*2].size() || r<drzewo[i*2+1].size())
        {
            if(l==drzewo[i*2].size())
            {
                drzewo[i].push_back(drzewo[i*2+1][r]);
                r++;
                continue;
            }
            if(r==drzewo[i*2+1].size())
            {
                drzewo[i].push_back(drzewo[i*2][l]);
                l++;
                continue;
            }
            if(drzewo[i*2][l]<=drzewo[i*2+1][r])
            {
                drzewo[i].push_back(drzewo[i*2][l]);
                l++;
            }
            else{
                drzewo[i].push_back(drzewo[i*2+1][r]);
                r++;
            }
        }
    }
    while(zap--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        maxx=0;
        wynikk=0;
        zapp(1,pot+1,pot*2+1,x+pot,y+pot);
        if(wynikk>z)
            cout<<"0\n";
        else cout<<"1\n";
    }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(l<drzewo[i*2].size() || r<drzewo[i*2+1].size())
      |               ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(l<drzewo[i*2].size() || r<drzewo[i*2+1].size())
      |                                       ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if(l==drzewo[i*2].size())
      |                ~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if(r==drzewo[i*2+1].size())
      |                ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 1216 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct
16 Correct 6 ms 1236 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 19272 KB Output is correct
2 Correct 175 ms 19204 KB Output is correct
3 Correct 169 ms 19404 KB Output is correct
4 Correct 159 ms 19196 KB Output is correct
5 Correct 180 ms 19240 KB Output is correct
6 Correct 110 ms 19252 KB Output is correct
7 Correct 110 ms 19216 KB Output is correct
8 Correct 149 ms 19208 KB Output is correct
9 Correct 33 ms 596 KB Output is correct
10 Correct 136 ms 19244 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 1216 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct
16 Correct 6 ms 1236 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct
19 Correct 550 ms 38532 KB Output is correct
20 Correct 448 ms 38528 KB Output is correct
21 Correct 332 ms 38616 KB Output is correct
22 Correct 388 ms 38640 KB Output is correct
23 Correct 320 ms 38656 KB Output is correct
24 Correct 287 ms 38560 KB Output is correct
25 Correct 282 ms 38564 KB Output is correct
26 Correct 347 ms 38652 KB Output is correct
27 Correct 369 ms 38632 KB Output is correct
28 Correct 456 ms 38528 KB Output is correct
29 Correct 370 ms 38668 KB Output is correct
30 Correct 373 ms 38632 KB Output is correct
31 Correct 390 ms 38596 KB Output is correct
32 Correct 428 ms 38608 KB Output is correct
33 Correct 425 ms 38604 KB Output is correct
34 Correct 245 ms 38728 KB Output is correct
35 Correct 260 ms 38632 KB Output is correct
36 Correct 262 ms 38624 KB Output is correct
37 Correct 270 ms 38644 KB Output is correct
38 Correct 262 ms 38648 KB Output is correct
39 Correct 349 ms 38600 KB Output is correct
40 Correct 244 ms 30148 KB Output is correct
41 Correct 325 ms 38576 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 1216 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct
16 Correct 6 ms 1236 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct
19 Execution timed out 3035 ms 185224 KB Time limit exceeded
20 Halted 0 ms 0 KB -