oj.uz

Submission #709768

# Submission time Handle Problem Language Result Execution time Memory
709768 2023-03-14T11:47:52 Z groshi Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 449 ms 262144 KB 
#include<iostream>
#include<set>
using namespace std;
set<int> drzewo[3000000];
int wynik[3000000];
int maxx=0;
int wynikk=0;
int pot=1;
void dodaj(int x)
{
    //cout<<"essa\n";
    wynikk=max(wynikk,wynik[x]);
    if(drzewo[x].size()==0)
        return;
    auto it=drzewo[x].end();
    it--;
    int mam=*it;
    if(maxx==0)
    {
        maxx=mam;
        return;
    }
    auto it2=drzewo[x].lower_bound(maxx);
    if(it2!=drzewo[x].begin())
    {
        it2--;
        if(it2!=drzewo[x].end())
            wynikk=max(wynikk,maxx+*it2);
    }
    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--;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        drzewo[i+pot].insert(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)
        {
            auto it=drzewo[i*2].end();
            it--;
            int jest=*it;
            auto it2=drzewo[i*2+1].lower_bound(jest);
            if(it2!=drzewo[i*2+1].begin())
            {
                it2--;
                if(it2!=drzewo[i*2+1].end())
                    wynik[i]=max(wynik[i],jest+*it2);
            }
        }
        drzewo[i]=drzewo[i*2];
        for(auto it=drzewo[i*2+1].begin();it!=drzewo[i*2+1].end();it++)
            drzewo[i].insert(*it);
    }
    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);
        //cout<<wynikk<<"\n";
        if(wynikk>z)
            cout<<"0\n";
        else cout<<"1\n";
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 141132 KB Output is correct
2 Correct 68 ms 141184 KB Output is correct
3 Correct 64 ms 141228 KB Output is correct
4 Correct 61 ms 141232 KB Output is correct
5 Correct 62 ms 141208 KB Output is correct
6 Correct 68 ms 141492 KB Output is correct
7 Correct 64 ms 141436 KB Output is correct
8 Correct 66 ms 141404 KB Output is correct
9 Correct 62 ms 141260 KB Output is correct
10 Correct 62 ms 141144 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 141132 KB Output is correct
2 Correct 68 ms 141184 KB Output is correct
3 Correct 64 ms 141228 KB Output is correct
4 Correct 61 ms 141232 KB Output is correct
5 Correct 62 ms 141208 KB Output is correct
6 Correct 68 ms 141492 KB Output is correct
7 Correct 64 ms 141436 KB Output is correct
8 Correct 66 ms 141404 KB Output is correct
9 Correct 62 ms 141260 KB Output is correct
10 Correct 62 ms 141144 KB Output is correct
11 Correct 66 ms 142072 KB Output is correct
12 Correct 73 ms 144460 KB Output is correct
13 Correct 76 ms 144548 KB Output is correct
14 Correct 73 ms 144580 KB Output is correct
15 Correct 72 ms 144596 KB Output is correct
16 Correct 72 ms 144536 KB Output is correct
17 Correct 73 ms 144016 KB Output is correct
18 Correct 67 ms 141760 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 196232 KB Output is correct
2 Correct 333 ms 196056 KB Output is correct
3 Correct 209 ms 154104 KB Output is correct
4 Correct 200 ms 154256 KB Output is correct
5 Correct 193 ms 154064 KB Output is correct
6 Correct 143 ms 153788 KB Output is correct
7 Correct 146 ms 153908 KB Output is correct
8 Correct 163 ms 152928 KB Output is correct
9 Correct 109 ms 142956 KB Output is correct
10 Correct 174 ms 152908 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 141132 KB Output is correct
2 Correct 68 ms 141184 KB Output is correct
3 Correct 64 ms 141228 KB Output is correct
4 Correct 61 ms 141232 KB Output is correct
5 Correct 62 ms 141208 KB Output is correct
6 Correct 68 ms 141492 KB Output is correct
7 Correct 64 ms 141436 KB Output is correct
8 Correct 66 ms 141404 KB Output is correct
9 Correct 62 ms 141260 KB Output is correct
10 Correct 62 ms 141144 KB Output is correct
11 Correct 66 ms 142072 KB Output is correct
12 Correct 73 ms 144460 KB Output is correct
13 Correct 76 ms 144548 KB Output is correct
14 Correct 73 ms 144580 KB Output is correct
15 Correct 72 ms 144596 KB Output is correct
16 Correct 72 ms 144536 KB Output is correct
17 Correct 73 ms 144016 KB Output is correct
18 Correct 67 ms 141760 KB Output is correct
19 Runtime error 259 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 141132 KB Output is correct
2 Correct 68 ms 141184 KB Output is correct
3 Correct 64 ms 141228 KB Output is correct
4 Correct 61 ms 141232 KB Output is correct
5 Correct 62 ms 141208 KB Output is correct
6 Correct 68 ms 141492 KB Output is correct
7 Correct 64 ms 141436 KB Output is correct
8 Correct 66 ms 141404 KB Output is correct
9 Correct 62 ms 141260 KB Output is correct
10 Correct 62 ms 141144 KB Output is correct
11 Correct 66 ms 142072 KB Output is correct
12 Correct 73 ms 144460 KB Output is correct
13 Correct 76 ms 144548 KB Output is correct
14 Correct 73 ms 144580 KB Output is correct
15 Correct 72 ms 144596 KB Output is correct
16 Correct 72 ms 144536 KB Output is correct
17 Correct 73 ms 144016 KB Output is correct
18 Correct 67 ms 141760 KB Output is correct
19 Runtime error 289 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -