Submission #1066774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066774		hasan2006	Radio Towers (IOI22_towers)	C++17	23 / 100	4057 ms	7392 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 count_dp(int l , int r , int k){
    int mx = 0 , i , j , x , y , s , f , m;
    d[r] = 1;
    f = r;
    set<int>st;
    int mn = a[r];
    for(i = r - 1; i >= l; i--){
        if(a[i] >  mx){
            d[i] = d[f];
            if(a[i] - k >= mn)
                mx = max(mx , a[i] - k);
            mn = min(mn , a[i]);
        }else{
            d[i] = d[f] + 1;
            mn= a[i];
            mx = 0;
            f = i;
        }
        d[i] = max(d[i] , d[i + 1]);
    }
}

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





int max_towers(int l ,int r , int k){
  //  if(k == 1)
  //      return d[r] - d[l] + 1;
    int mx = 0 , i , j , x , y , s , f , m;
    dp[r] = 1;
    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 'void count_dp(int, int, int)':
towers.cpp:26:22: warning: unused variable 'j' [-Wunused-variable]
   26 |     int mx = 0 , i , j , x , y , s , f , m;
      |                      ^
towers.cpp:26:26: warning: unused variable 'x' [-Wunused-variable]
   26 |     int mx = 0 , i , j , x , y , s , f , m;
      |                          ^
towers.cpp:26:30: warning: unused variable 'y' [-Wunused-variable]
   26 |     int mx = 0 , i , j , x , y , s , f , m;
      |                              ^
towers.cpp:26:34: warning: unused variable 's' [-Wunused-variable]
   26 |     int mx = 0 , i , j , x , y , s , f , m;
      |                                  ^
towers.cpp:26:42: warning: unused variable 'm' [-Wunused-variable]
   26 |     int mx = 0 , i , j , x , y , s , f , m;
      |                                          ^
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:60:22: warning: unused variable 'j' [-Wunused-variable]
   60 |     int mx = 0 , i , j , x , y , s , f , m;
      |                      ^
towers.cpp:60:26: warning: unused variable 'x' [-Wunused-variable]
   60 |     int mx = 0 , i , j , x , y , s , f , m;
      |                          ^
towers.cpp:60:30: warning: unused variable 'y' [-Wunused-variable]
   60 |     int mx = 0 , i , j , x , y , s , f , m;
      |                              ^
towers.cpp:60:34: warning: unused variable 's' [-Wunused-variable]
   60 |     int mx = 0 , i , j , x , y , s , f , m;
      |                                  ^
towers.cpp:60:42: warning: unused variable 'm' [-Wunused-variable]
   60 |     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