Submission #1216399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216399		ASGA_RedSea	Radio Towers (IOI22_towers)	C++20	4 / 100	3741 ms	2452 KiB

towers

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"towers.h"


int n;
vector<int>a;


int spt,k;

void init(int N,vector<int>H){
    n=N;
    a=H;

    int l=1,r=n-2;
    while(l<n&&a[l-1]<=a[l])l++;l--;
    while(r>=0&&a[r]>=a[r+1])r--;r++;

    spt=2;
    if(l==r){spt=1;k=l;}
}

struct sgt{
    vector<int>s;
    int lg,sz;
    sgt(int n){
        lg=__lg(n)+1;sz=1<<lg;
        s.assign(sz*2,1e9);
    }
    void edit(int i,int v){
        s[(i+=sz)]=v;
        while(i>1){
            i>>=1;
            s[i]=min(s[i*2],s[i*2+1]);
        }
    }
    int get(int L,int R,int l,int r,int i){
        if(l>R||L>r)return 1e9;
        if(L<=l&&r<=R)return s[i];
        return min(get(L,R,l,(l+r)/2,i*2),get(L,R,(l+r)/2+1,r,i*2+1));
    }
    int get(int l,int r){return get(++l,++r,1,sz,1);}
};


int max_towers(int l,int r,int dd){
    if(spt==1){
        return(k>=l&&k<=r&&a[l]<=a[k]-dd&&a[r]<=a[k]-dd?2:1);
    }

    vector<int>d(n,0);
    d[l]=1;
    sgt s(n);
    for(int i=l+1;i<=r;i++){
        d[i]=d[i-1];

        //int g=s.get(a[i]+d);
    }
    return d[r];
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23