oj.uz

Submission #692536

# Submission time Handle Problem Language Result Execution time Memory
692536 2023-02-01T19:08:35 Z Mer123haba456 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
34 / 100
 716 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
#define N lli(2e6)
#define MOD lli(1e9 + 7)
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0);
#define heps(v) v.begin(),v.end()
typedef vector<lli> vlli;
typedef pair<lli,lli> plli;
typedef pair<lli,plli> pplli;
typedef pair<plli,plli> ppplli;
typedef vector<plli> vplli;
typedef vector<pplli> vpplli;
typedef map<lli,lli> mlli;
typedef set<lli> slli;

lli t,n,m,k;

string str;

lli seg[N];
plli enbseg[N];
slli karseg[N];

vlli vect;

plli operator+(plli a,lli b){
    if(b > a.first){
        a.second = a.first;
        a.first = b;
    }else if(b > a.second && b != a.first){
        a.second = b;
    }
    return a;
}

plli operator+(plli a,plli b){
    a = a + b.first;
    a = a + b.second;
    return a;
}

bool operator>(plli a,plli b){
    lli sua = (a.second == -1 ? 0 : a.first + a.second);
    lli sub = (b.second == -1 ? 0 : b.first + b.second);
    return sua > sub;
}

void yap(lli v,lli l,lli r){
    if(l == r){
        plli su = {-1,-1};
        seg[v] = vect[l];
        enbseg[v] = {vect[l],-1};
        karseg[v].insert(vect[l]);
        return;
    }
    lli m = (l+r)/2;
    yap(2*v,l,m);
    yap(2*v+1,m+1,r);
    seg[v] = max(seg[2*v], seg[2*v+1]);
    enbseg[v] = enbseg[2*v];
    if(enbseg[2*v+1] > enbseg[2*v])
        enbseg[v] = enbseg[2*v+1];
    plli tmp = {seg[2*v],-1};
    auto de = karseg[2*v+1].lower_bound(seg[2*v]);
    if(de != karseg[2*v+1].begin()){
        de--;
        tmp.second = *de;
    }
    if(tmp > enbseg[v])
        enbseg[v] = tmp;
    for(auto it = karseg[2*v].begin();it!=karseg[2*v].end();it++)
        karseg[v].insert(*it);
    for(auto it = karseg[2*v+1].begin();it!=karseg[2*v+1].end();it++)
        karseg[v].insert(*it);
}

ppplli getir(lli v,lli l,lli r,lli list,lli rist,lli ist){
    if(list<= l && r <= rist){
        auto de = karseg[v].lower_bound(ist);
        lli dond = -1;
        if(de != karseg[v].begin()){
            de--;
            dond = *de;
        }
        ppplli su = {enbseg[v],{max(seg[v],ist),dond}};
        return su;
    }
    lli m = (l+r)/2;
    if(rist<=m)
        return getir(2*v,l,m,list,rist,ist);
    else if(list > m)
        return getir(2*v+1,m+1,r,list,rist,ist);
    else{
        ppplli su = getir(2*v,l,m,list,rist,ist); 
        plli ilk = {-1,-1};
        if(su.second.second < ist)
            ilk = {ist,su.second.second};
        if(su.first > ilk)
            ilk = su.first;
        ppplli sui = getir(2*v+1,m+1,r,list,rist, su.second.first);
        plli iki = {-1,-1};
        if(sui.second.second < su.second.first)
            iki = {su.second.first, sui.second.second};
        if(sui.first > iki)
            iki = sui.first;
        if(iki > ilk)
            ilk = iki;
        ppplli dond = {ilk, {max(su.second.first,sui.second.first),max(su.second.second,sui.second.second)}};
        return dond;
    }
}

int main(){
    fast_io
    /*slli se = {0,5,7,8};
    auto it = se.lower_bound(0);
    cout << (it == se.begin()) << endl;*/
    cin >> n >> t;
    for(lli i = 0;i<n;i++){
        cin >> k;
        vect.push_back(k);
    }
    yap(1,0,n-1);
    while(t--){
        lli a,b,c;
        cin >> a >> b >> c;
        a--;
        b--;
        plli su = getir(1,0,n-1,a,b,-1).first;
        if(su.second == -1 || su.first == -1 || (c >= su.first + su.second))
            cout << "1" << endl;
        else
            cout << "0" << endl;
    }
}

Compilation message

sortbooks.cpp: In function 'void yap(lli, lli, lli)':
sortbooks.cpp:52:14: warning: variable 'su' set but not used [-Wunused-but-set-variable]
   52 |         plli su = {-1,-1};
      |              ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94152 KB Output is correct
2 Correct 45 ms 94252 KB Output is correct
3 Correct 45 ms 94276 KB Output is correct
4 Correct 45 ms 94212 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 48 ms 94612 KB Output is correct
7 Correct 45 ms 94436 KB Output is correct
8 Correct 44 ms 94612 KB Output is correct
9 Correct 46 ms 94284 KB Output is correct
10 Correct 45 ms 94232 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94152 KB Output is correct
2 Correct 45 ms 94252 KB Output is correct
3 Correct 45 ms 94276 KB Output is correct
4 Correct 45 ms 94212 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 48 ms 94612 KB Output is correct
7 Correct 45 ms 94436 KB Output is correct
8 Correct 44 ms 94612 KB Output is correct
9 Correct 46 ms 94284 KB Output is correct
10 Correct 45 ms 94232 KB Output is correct
11 Correct 54 ms 95148 KB Output is correct
12 Correct 57 ms 97712 KB Output is correct
13 Correct 59 ms 97756 KB Output is correct
14 Correct 64 ms 97968 KB Output is correct
15 Correct 66 ms 97984 KB Output is correct
16 Correct 60 ms 97868 KB Output is correct
17 Correct 57 ms 97012 KB Output is correct
18 Correct 53 ms 95148 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 464 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 716 ms 155664 KB Output is correct
2 Correct 595 ms 155664 KB Output is correct
3 Correct 331 ms 113608 KB Output is correct
4 Correct 336 ms 113440 KB Output is correct
5 Correct 320 ms 113476 KB Output is correct
6 Correct 262 ms 113324 KB Output is correct
7 Correct 278 ms 113416 KB Output is correct
8 Correct 271 ms 112428 KB Output is correct
9 Correct 198 ms 96044 KB Output is correct
10 Correct 267 ms 112432 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94152 KB Output is correct
2 Correct 45 ms 94252 KB Output is correct
3 Correct 45 ms 94276 KB Output is correct
4 Correct 45 ms 94212 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 48 ms 94612 KB Output is correct
7 Correct 45 ms 94436 KB Output is correct
8 Correct 44 ms 94612 KB Output is correct
9 Correct 46 ms 94284 KB Output is correct
10 Correct 45 ms 94232 KB Output is correct
11 Correct 54 ms 95148 KB Output is correct
12 Correct 57 ms 97712 KB Output is correct
13 Correct 59 ms 97756 KB Output is correct
14 Correct 64 ms 97968 KB Output is correct
15 Correct 66 ms 97984 KB Output is correct
16 Correct 60 ms 97868 KB Output is correct
17 Correct 57 ms 97012 KB Output is correct
18 Correct 53 ms 95148 KB Output is correct
19 Runtime error 392 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 43 ms 94152 KB Output is correct
2 Correct 45 ms 94252 KB Output is correct
3 Correct 45 ms 94276 KB Output is correct
4 Correct 45 ms 94212 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 48 ms 94612 KB Output is correct
7 Correct 45 ms 94436 KB Output is correct
8 Correct 44 ms 94612 KB Output is correct
9 Correct 46 ms 94284 KB Output is correct
10 Correct 45 ms 94232 KB Output is correct
11 Correct 54 ms 95148 KB Output is correct
12 Correct 57 ms 97712 KB Output is correct
13 Correct 59 ms 97756 KB Output is correct
14 Correct 64 ms 97968 KB Output is correct
15 Correct 66 ms 97984 KB Output is correct
16 Correct 60 ms 97868 KB Output is correct
17 Correct 57 ms 97012 KB Output is correct
18 Correct 53 ms 95148 KB Output is correct
19 Runtime error 464 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -