Submission #1066726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066726		hasan2006	Radio Towers (IOI22_towers)	C++17	23 / 100	4091 ms	3672 KiB

towers

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
int b[N] , dp[N] , c[N] , d[N] , n , t[N] ;
vector<int>a;


void init(int n , vector<int>a){
    ::a = a;
    ::n = n;
}


void pushup(int i){
    t[i] = max(t[2 * i] , t[2 * i + 1]);
}

void add(int i , int l , int r , int tl , int tr , int x){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr){
        t[i] = x;
    }else {
        add(2 * i , l , m , tl , tr , x);
        add(2 * i + 1 , m + 1 , r , tl , tr , x);
        pushup(i);
    }
}

ll get(int i , int l , int r , int tl , int tr){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return 0;
    if(l >= tl && r <= tr){
        return t[i];
    }else {
        return max(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr));
    }
}




int max_towers(int l ,int r , int k){
    int mx = 0 , i , j , x , y , s , f , m;
    dp[r] = 1 , d[r] = a[r];
    for(i = l; i <= r; i++)
        add(1 ,1 , n , i + 1 , i + 1 , a[i]);
    f = r;
    set<int>st;
    int mn = a[r];
    for(i = r - 1; i >= l; i--){
        if(a[i] >  mx){
            dp[i] = dp[f];
            if(a[i] - k >= mn)
                mx = max(mx , a[i] - k);
            mn = min(mn , a[i]);
        }else{
            dp[i] = dp[f] + 1;
            mn= a[i];
            mx = 0;
            f = i;
        }
        dp[i] = max(dp[i] , dp[i + 1]);
    }
    return dp[l];
}
/*
int main(){
    TL;

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    /*
    init(7, {10, 20, 60, 40, 50, 30, 70});
    cout<<max_towers(0 , 6, 17)<<"\n";
}*/
// Author : حسن

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:62:22: warning: unused variable 'j' [-Wunused-variable]
   62 |     int mx = 0 , i , j , x , y , s , f , m;
      |                      ^
towers.cpp:62:26: warning: unused variable 'x' [-Wunused-variable]
   62 |     int mx = 0 , i , j , x , y , s , f , m;
      |                          ^
towers.cpp:62:30: warning: unused variable 'y' [-Wunused-variable]
   62 |     int mx = 0 , i , j , x , y , s , f , m;
      |                              ^
towers.cpp:62:34: warning: unused variable 's' [-Wunused-variable]
   62 |     int mx = 0 , i , j , x , y , s , f , m;
      |                                  ^
towers.cpp:62:42: warning: unused variable 'm' [-Wunused-variable]
   62 |     int mx = 0 , i , j , x , y , s , f , m;
      |                                          ^

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