Submission #707131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707131	2023-03-08T13:42:54 Z	Karuk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3000 ms	224340 KB

sortbooks

#include<bits/stdc++.h>///3:27- func start///3:41 end
using namespace std;
vector<vector<int>>st;
int score[4000000];
int k=1;
vector<int>ind;
int max(int a,int b) {
    return a>b?a:b;
}
void push(int from,int to,int cur=1,int beg=0,int en=k-1) {
    if(from>en || to<beg)return;
    if(from<=beg && en<=to){ind.push_back(cur);return;}
    int mid=(beg+en)/2;
    push(from,to,cur*2,beg,mid);
    push(from,to,cur*2+1,mid+1,en);
}
int combine(int i,int j) {
    if(st[j].size()==0 || st[i].size()==0)return score[i];
    int mx=st[i].back();
    int ans=max(score[i],score[j]);
    int ind=lower_bound(st[j].begin(),st[j].end(),mx)-st[j].begin();
    ind--;
    if(ind>=0)ans=max(ans,mx+st[j][ind]);
    return ans;
}
int maxw(int l,int r) {
    ind.clear();
    push(l,r);
    int ans=score[ind.back()];
    for(int i=1;i<ind.size();i++) {
        ans=max(ans,combine(ind[i-1],ind[i]));
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    while(k<n){k<<=1;}
    st.resize(k*2);
    for(int i=0;i<n;i++)st[i+k].push_back(a[i]);
    for(int i=k-1;i>0;i--) {
        int p1=0,p2=0;
        while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
            if(st[i*2][p1]<st[i*2+1][p2]) {
                st[i].push_back(st[i*2][p1]);
                p1++;
            } else {
                st[i].push_back(st[i*2+1][p2]);
                p2++;
            }
        }
        while(p1<st[i*2].size()) {
            st[i].push_back(st[i*2][p1]);
            p1++;
        }
        while(p2<st[i*2+1].size()) {
            st[i].push_back(st[i*2+1][p2]);
            p2++;
        }
        score[i]=combine(2*i,2*i+1);
    }
    for(int i=0;i<m;i++) {
        int l,r,w;cin>>l>>r>>w;
        l--;r--;
        int as=maxw(l,r);
        if(as<=w)cout<<1<<'\n';
        else cout<<0<<'\n';
    }
    return 0;
}
/**
5 6
3 2 9 8 1
*/

Compilation message

sortbooks.cpp: In function 'int maxw(int, int)':
sortbooks.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<ind.size();i++) {
      |                 ~^~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:45:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(p1<st[i*2].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while(p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2932 ms	221324 KB	Output is correct
2	Correct	2948 ms	224340 KB	Output is correct
3	Correct	2912 ms	222008 KB	Output is correct
4	Execution timed out	3006 ms	223992 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-