Submission #835130

#TimeUsernameProblemLanguageResultExecution timeMemory
835130gagik_2007Radio Towers (IOI22_towers)C++17
23 / 100
4093 ms12144 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=100007; ll n,m,k; vector<int>a; struct Node{ int mx; int mxind; int mn; int mnind; Node():mx(0),mn(0),mxind(0),mnind(0){} void bld(int vl, int ind){ mx=mn=vl; mxind=mnind=ind; } void join(const Node& lft, const Node& rgh){ if(lft.mx>=rgh.mx){ mx=lft.mx; mxind=lft.mxind; } else{ mx=rgh.mx; mxind=rgh.mxind; } if(lft.mn<=rgh.mn){ mn=lft.mn; mnind=lft.mnind; } else{ mn=rgh.mn; mnind=rgh.mnind; } } }; Node t[4*N]; void build(int v, int tl, int tr){ if(tl==tr){ t[v].bld(a[tl], tl); } else{ int tm=(tl+tr)/2; build(2*v,tl,tm); build(2*v+1,tm+1,tr); t[v].join(t[2*v],t[2*v+1]); } } pair<int,int> get_max(int v, int tl, int tr, int l, int r){ if(l>r)return {0,0}; if(tl==l&&tr==r)return {t[v].mx, t[v].mxind}; else{ int tm=(tl+tr)/2; return max(get_max(2*v,tl,tm,l,min(tm,r)), get_max(2*v+1,tm+1,tr,max(tm+1,l),r)); } } pair<int,int> get_min(int v, int tl, int tr, int l, int r){ if(l>r)return {MOD,MOD}; if(tl==l&&tr==r)return {t[v].mn,t[v].mnind}; else{ int tm=(tl+tr)/2; return min(get_min(2*v,tl,tm,l,min(tm,r)), get_min(2*v+1,tm+1,tr,max(tm+1,l),r)); } } int recurs(int l, int r, int vl, int d){ if(l>r)return 0; int mx=get_max(1,0,n-1,l,r).ss, mn=get_min(1,0,n-1,l,r).ss; if(a[mn]>vl-d)return 0; int lft=recurs(l,mx-1,a[mx],d); int rgh=recurs(mx+1,r,a[mx],d); // cout<<l<<" "<<r<<" "<<vl<<" "<<d<<": "; // cout<<a[mn]<<", "<<a[mx]<<", "; if(lft==0&&rgh==0){ // cout<<1<<endl; return 1; } // cout<<lft+rgh<<endl; return lft+rgh; } void init(int NN, vector<int> H) { n=NN; a=H; build(1,0,n-1); } int max_towers(int L, int R, int D) { return recurs(L,R,2e9+7,D); }

Compilation message (stderr)

towers.cpp: In constructor 'Node::Node()':
towers.cpp:22:9: warning: 'Node::mn' will be initialized after [-Wreorder]
   22 |     int mn;
      |         ^~
towers.cpp:21:9: warning:   'int Node::mxind' [-Wreorder]
   21 |     int mxind;
      |         ^~~~~
towers.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Node():mx(0),mn(0),mxind(0),mnind(0){}
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...