oj.uz

Submission #692537

# Submission time Handle Problem Language Result Execution time Memory
692537 2023-02-01T19:13:00 Z Mer123haba456 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1708 ms 237012 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int lli;
typedef long double ld;
#define N lli(1e6)
#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;*/
    scanf("%d %d",&n,&t);
    for(lli i = 0;i<n;i++){
        scanf("%d",&k);
        vect.push_back(k);
    }
    yap(1,0,n-1);
    while(t--){
        lli a,b,c;
        scanf("%d %d %d",&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))
            printf("1\n");
        else
            printf("0\n");
    }
}

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};
      |              ^~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d %d",&n,&t);
      |     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
sortbooks.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47268 KB Output is correct
3 Correct 22 ms 47336 KB Output is correct
4 Correct 23 ms 47264 KB Output is correct
5 Correct 25 ms 47388 KB Output is correct
6 Correct 23 ms 47524 KB Output is correct
7 Correct 28 ms 47444 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47268 KB Output is correct
3 Correct 22 ms 47336 KB Output is correct
4 Correct 23 ms 47264 KB Output is correct
5 Correct 25 ms 47388 KB Output is correct
6 Correct 23 ms 47524 KB Output is correct
7 Correct 28 ms 47444 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47340 KB Output is correct
11 Correct 28 ms 48136 KB Output is correct
12 Correct 35 ms 50496 KB Output is correct
13 Correct 35 ms 50552 KB Output is correct
14 Correct 36 ms 50560 KB Output is correct
15 Correct 35 ms 50668 KB Output is correct
16 Correct 35 ms 50624 KB Output is correct
17 Correct 32 ms 49868 KB Output is correct
18 Correct 27 ms 47956 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 113800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 103248 KB Output is correct
2 Correct 444 ms 103336 KB Output is correct
3 Correct 172 ms 61100 KB Output is correct
4 Correct 172 ms 61096 KB Output is correct
5 Correct 174 ms 61064 KB Output is correct
6 Correct 124 ms 61072 KB Output is correct
7 Correct 125 ms 61076 KB Output is correct
8 Correct 131 ms 60304 KB Output is correct
9 Correct 61 ms 47672 KB Output is correct
10 Correct 138 ms 60328 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47268 KB Output is correct
3 Correct 22 ms 47336 KB Output is correct
4 Correct 23 ms 47264 KB Output is correct
5 Correct 25 ms 47388 KB Output is correct
6 Correct 23 ms 47524 KB Output is correct
7 Correct 28 ms 47444 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47340 KB Output is correct
11 Correct 28 ms 48136 KB Output is correct
12 Correct 35 ms 50496 KB Output is correct
13 Correct 35 ms 50552 KB Output is correct
14 Correct 36 ms 50560 KB Output is correct
15 Correct 35 ms 50668 KB Output is correct
16 Correct 35 ms 50624 KB Output is correct
17 Correct 32 ms 49868 KB Output is correct
18 Correct 27 ms 47956 KB Output is correct
19 Correct 1678 ms 237012 KB Output is correct
20 Correct 1708 ms 236736 KB Output is correct
21 Correct 1208 ms 236620 KB Output is correct
22 Correct 1208 ms 236624 KB Output is correct
23 Correct 1196 ms 236592 KB Output is correct
24 Correct 860 ms 236496 KB Output is correct
25 Correct 885 ms 236484 KB Output is correct
26 Correct 1058 ms 236616 KB Output is correct
27 Correct 1047 ms 236640 KB Output is correct
28 Correct 1103 ms 236624 KB Output is correct
29 Correct 1163 ms 236852 KB Output is correct
30 Correct 1233 ms 236740 KB Output is correct
31 Correct 1197 ms 236764 KB Output is correct
32 Correct 1162 ms 236716 KB Output is correct
33 Correct 1178 ms 236748 KB Output is correct
34 Correct 838 ms 236312 KB Output is correct
35 Correct 839 ms 236368 KB Output is correct
36 Correct 834 ms 236312 KB Output is correct
37 Correct 833 ms 236124 KB Output is correct
38 Correct 841 ms 236476 KB Output is correct
39 Correct 1083 ms 235348 KB Output is correct
40 Correct 701 ms 166624 KB Output is correct
41 Correct 278 ms 78148 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47268 KB Output is correct
3 Correct 22 ms 47336 KB Output is correct
4 Correct 23 ms 47264 KB Output is correct
5 Correct 25 ms 47388 KB Output is correct
6 Correct 23 ms 47524 KB Output is correct
7 Correct 28 ms 47444 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47340 KB Output is correct
11 Correct 28 ms 48136 KB Output is correct
12 Correct 35 ms 50496 KB Output is correct
13 Correct 35 ms 50552 KB Output is correct
14 Correct 36 ms 50560 KB Output is correct
15 Correct 35 ms 50668 KB Output is correct
16 Correct 35 ms 50624 KB Output is correct
17 Correct 32 ms 49868 KB Output is correct
18 Correct 27 ms 47956 KB Output is correct
19 Runtime error 166 ms 113800 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -