oj.uz

Submission #491763

# Submission time Handle Problem Language Result Execution time Memory
491763 2021-12-04T09:37:16 Z reni Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 457 ms 262148 KB 
#include<iostream>
#include<stack>
#define endl '\n'
#include<vector>
using namespace std;
long long maxi[5000000], a[5000000];
stack< pair<long long,long long> >st;
vector< pair< pair<long long,long long>, long long > >mm[10000000];
bool rez[10000000];
void update(long long le,long long ri,long long node,long long ind,long long val)
{
    if(le>node || ri<node)return;
    if(le==ri)
    {
        maxi[ind]=max(maxi[ind],val);return;
    }
    long long mid=(le+ri)/2;

    update(le,mid,node,2*ind,val);
    update(mid+1,ri,node,2*ind+1,val);

    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

}
long long query(long long le,long long ri,long long l,long long r,long long ind)
{
    if(le>r || ri<l)return 0;

    if(l<=le && ri<=r)
    {
        return maxi[ind];
    }
    long long mid=(le+ri)/2;

    long long r1,r2;

    r1=query(le,mid,l,r,2*ind);
    r2=query(mid+1,ri,l,r,2*ind+1);

    return max(r1,r2);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long i,j,n,m,l,r,k,p;

    cin>>n>>m;

    for(i=1;i<=n;i++)
    {
        cin>>a[i];

    }

    for(i=1;i<=m;i++)
    {
        cin>>l>>r>>k;
        mm[r].push_back({ {l,k}, i});
    }

    for(i=1;i<=n;i++)
    {
        while(!st.empty() && st.top().first<=a[i])st.pop();
        if(st.empty())
        {
        }
        else
        {
            update(1,n,st.top().second,1,a[i]+st.top().first);
        }


        for(j=0;j<mm[i].size();j++)
        {
            long long ll=mm[i][j].first.first,
             k=mm[i][j].first.second,
              ind=mm[i][j].second;

            rez[ind]=max(rez[ind],query(1,n,ll,i,1)<=k);
        }
         st.push({a[i],i});

    }
    for(i=1;i<=m;i++)
    {
        cout<<rez[i]<<endl;
    }
}


/*
5 3
3 5 1 8 2
1 3 6
2 5 3
3 5 10

*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(j=0;j<mm[i].size();j++)
      |                 ~^~~~~~~~~~~~~
sortbooks.cpp:47:29: warning: unused variable 'p' [-Wunused-variable]
   47 |     long long i,j,n,m,l,r,k,p;
      |                             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235120 KB Output is correct
2 Correct 101 ms 235104 KB Output is correct
3 Correct 102 ms 235172 KB Output is correct
4 Correct 113 ms 235076 KB Output is correct
5 Correct 105 ms 235164 KB Output is correct
6 Correct 107 ms 235172 KB Output is correct
7 Correct 115 ms 235076 KB Output is correct
8 Correct 106 ms 235064 KB Output is correct
9 Correct 120 ms 235224 KB Output is correct
10 Correct 106 ms 235148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235120 KB Output is correct
2 Correct 101 ms 235104 KB Output is correct
3 Correct 102 ms 235172 KB Output is correct
4 Correct 113 ms 235076 KB Output is correct
5 Correct 105 ms 235164 KB Output is correct
6 Correct 107 ms 235172 KB Output is correct
7 Correct 115 ms 235076 KB Output is correct
8 Correct 106 ms 235064 KB Output is correct
9 Correct 120 ms 235224 KB Output is correct
10 Correct 106 ms 235148 KB Output is correct
11 Correct 116 ms 235424 KB Output is correct
12 Correct 113 ms 235296 KB Output is correct
13 Correct 108 ms 235396 KB Output is correct
14 Correct 111 ms 235512 KB Output is correct
15 Correct 114 ms 235436 KB Output is correct
16 Correct 123 ms 235424 KB Output is correct
17 Correct 121 ms 235352 KB Output is correct
18 Correct 106 ms 235456 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 457 ms 262148 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 201 ms 241636 KB Output is correct
2 Correct 188 ms 241708 KB Output is correct
3 Correct 176 ms 239428 KB Output is correct
4 Correct 175 ms 239424 KB Output is correct
5 Correct 180 ms 239500 KB Output is correct
6 Correct 161 ms 239512 KB Output is correct
7 Correct 163 ms 239556 KB Output is correct
8 Correct 180 ms 239508 KB Output is correct
9 Correct 136 ms 238332 KB Output is correct
10 Correct 182 ms 239496 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235120 KB Output is correct
2 Correct 101 ms 235104 KB Output is correct
3 Correct 102 ms 235172 KB Output is correct
4 Correct 113 ms 235076 KB Output is correct
5 Correct 105 ms 235164 KB Output is correct
6 Correct 107 ms 235172 KB Output is correct
7 Correct 115 ms 235076 KB Output is correct
8 Correct 106 ms 235064 KB Output is correct
9 Correct 120 ms 235224 KB Output is correct
10 Correct 106 ms 235148 KB Output is correct
11 Correct 116 ms 235424 KB Output is correct
12 Correct 113 ms 235296 KB Output is correct
13 Correct 108 ms 235396 KB Output is correct
14 Correct 111 ms 235512 KB Output is correct
15 Correct 114 ms 235436 KB Output is correct
16 Correct 123 ms 235424 KB Output is correct
17 Correct 121 ms 235352 KB Output is correct
18 Correct 106 ms 235456 KB Output is correct
19 Correct 324 ms 247892 KB Output is correct
20 Correct 313 ms 247920 KB Output is correct
21 Correct 313 ms 248504 KB Output is correct
22 Correct 284 ms 248464 KB Output is correct
23 Correct 281 ms 248420 KB Output is correct
24 Correct 305 ms 244540 KB Output is correct
25 Correct 243 ms 244564 KB Output is correct
26 Correct 269 ms 244340 KB Output is correct
27 Correct 278 ms 244168 KB Output is correct
28 Correct 304 ms 244036 KB Output is correct
29 Correct 269 ms 243772 KB Output is correct
30 Correct 290 ms 243836 KB Output is correct
31 Correct 279 ms 243900 KB Output is correct
32 Correct 276 ms 243780 KB Output is correct
33 Correct 306 ms 243804 KB Output is correct
34 Correct 244 ms 243948 KB Output is correct
35 Correct 251 ms 243960 KB Output is correct
36 Correct 235 ms 243904 KB Output is correct
37 Correct 238 ms 243992 KB Output is correct
38 Correct 258 ms 244100 KB Output is correct
39 Correct 266 ms 244660 KB Output is correct
40 Correct 225 ms 242308 KB Output is correct
41 Correct 259 ms 244024 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235120 KB Output is correct
2 Correct 101 ms 235104 KB Output is correct
3 Correct 102 ms 235172 KB Output is correct
4 Correct 113 ms 235076 KB Output is correct
5 Correct 105 ms 235164 KB Output is correct
6 Correct 107 ms 235172 KB Output is correct
7 Correct 115 ms 235076 KB Output is correct
8 Correct 106 ms 235064 KB Output is correct
9 Correct 120 ms 235224 KB Output is correct
10 Correct 106 ms 235148 KB Output is correct
11 Correct 116 ms 235424 KB Output is correct
12 Correct 113 ms 235296 KB Output is correct
13 Correct 108 ms 235396 KB Output is correct
14 Correct 111 ms 235512 KB Output is correct
15 Correct 114 ms 235436 KB Output is correct
16 Correct 123 ms 235424 KB Output is correct
17 Correct 121 ms 235352 KB Output is correct
18 Correct 106 ms 235456 KB Output is correct
19 Runtime error 457 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -