Submission #509813

#	Time	Username	Problem	Language	Result	Execution time	Memory
509813		Belgutei	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1659 ms	138632 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

vector<int> mx[30];
vector<int> mr[30];
vector<int> v[30];
int val;
int n,m;
int level,zereg[30];
int l,r,k;
int a,b;
int ret,tur;
int maximum_val;
bool check;

int go(int MX, int k, int x){
    a=zereg[level-k]*x;
    b=zereg[level-k]*(x+1)-1;
    // mr-iin k dahi level // a -> b
    if(MX<=mr[k][a]) return 0;
    while(a<b){
        int mid=(a+b+1)/2;
        if(mr[k][mid]<MX){
            a=mid;
        }
        else b=mid-1;
    }
    return mr[k][a]+MX;
}

void construct_v(){
    for(int i=0; i<zereg[level]; i++){
        v[level].pb(0);
    }
    for(int i=level-1; i>=0; i--){
        for(int j=0; j<zereg[i]; j++){
            v[i].pb(max(go(mx[i+1][j*2],i+1,j*2+1),max(v[i+1][j*2],v[i+1][j*2+1])));
        }
    }
}

void dfs(int k, int x){
    if(check==0) return;
    int y=zereg[level-k]*x;
    int z=zereg[level-k]*(x+1)-1;
    if(l<=y && z<=r){
        if(maximum_val==-1){
            maximum_val=mx[k][x];
            if(v[k][x]>val) check=0;
            return;
        }
        if(go(maximum_val,k,x)>val || v[k][x]>val){
            check=0;
        }
        maximum_val=max(maximum_val,mx[k][x]);
        return;
    }
    if(z<l || y>r || k==level) return;
    dfs(k+1,x*2);
    dfs(k+1,x*2+1);
}

int main(){
    IOS
    cin>>n>>m;
    zereg[0]=1;
    for(int i=0; i<=30; i++){
        if(zereg[i]>=n){
            level=i;
            break;
        }
        zereg[i+1]=zereg[i]*2;
    }
    for(int i=0; i<n; i++){
        cin>>val;
        mx[level].pb(val);
        mr[level].pb(val);
    }
    for(int i=n; i<zereg[level]; i++){
        mx[level].pb(0);
        mr[level].pb(1e9+5);
    }
    for(int i=level-1; i>=0; i--){
        for(int j=1; j<mx[i+1].size(); j+=2){
            mx[i].pb(max(mx[i+1][j],mx[i+1][j-1]));
        }
    }
    int urt=1;
    for(int i=level-1; i>=0; i--){
        urt*=2;
        for(int j=0; j<zereg[level]; j+=urt){
            l=j;
            r=j+urt/2;
            while(l!=j+urt/2 || r!=j+urt){
                if(l==j+urt/2){
                    mr[i].pb(mr[i+1][r]);
                    r++;
                    continue;
                }
                if(r==j+urt){
                    mr[i].pb(mr[i+1][l]);
                    l++;
                    continue;
                }
                if(mr[i+1][l]>=mr[i+1][r]){
                    mr[i].pb(mr[i+1][r]);
                    r++;
                }
                else{
                    mr[i].pb(mr[i+1][l]);
                    l++;
                }
            }
        }
    }
    construct_v(); 
    //
    
    while(m--){
        cin>>l>>r>>val;
        l--;
        r--;
        maximum_val=-1;
        check=1;
        dfs(0,0);
        cout<<check<<'\n';
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int j=1; j<mx[i+1].size(); j+=2){
      |                      ~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23