Submission #1225759

#TimeUsernameProblemLanguageResultExecution timeMemory
1225759sitingfakeGlobal Warming (CEOI18_glo)C++20
100 / 100
82 ms5256 KiB
#include<bits/stdc++.h> using namespace std; // define #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define ll long long #define ld double #define ii pair<int,int> #define se second #define fi first #define iii pair<int,ii> #define all(v) v.begin(),v.end() #define bit(x,i) (((x)>>(i))&1LL) #define flip(x,i) ((x)^(1LL<<(i))) #define ms(d,x) memset(d,x,sizeof(d)) #define sitingfake 1 #define orz 1 //constant const ll mod = 1e9 + 7; const long long linf = 4557430888798830399; const int inf = 1061109567; const int maxarr = 1e6 + 5; const int dx[] = {0,1,-1,0}; const int dy[] = {1,0,0,-1}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } inline void Plus(ll & a ,ll b) { b %= mod; a += b; if(a >= mod) a -= mod; if(a < 0) a += mod; return; } inline void Mul(ll & a, ll b) { a %= mod; b %= mod; a *= b; a %= mod; return; } //code const int maxn = 2e5 + 7; int a[maxn] , id[maxn]; int bit[maxn]; int l[maxn] , r[maxn]; int n , x; vector <int> P; void up(int x , int val , int type) { if(type == 1) { for(;x > 0; x -= (x & -x)) bit[x] = max(bit[x] , val); } else { for(;x <= n; x += (x & -x)) bit[x] = max(bit[x] , val); } } int get(int x,int type) { int ans = 0; if(type == 1) { for(;x <= n; x += (x & -x)) ans = max(bit[x] , ans); } else { for(;x > 0; x -= (x & -x)) ans = max(bit[x] , ans); } return ans; } void Reform() { for(int i = 1; i <= n; i++) { P.push_back(a[i]); } sort(all(P)); P.resize(unique(all(P)) - P.begin()); for(int i = 1; i <= n; i++) { id[i] = lower_bound(all(P) , a[i]) - P.begin() + 1; } } void solve(void) { cin >> n >> x; for(int i = 1; i <= n; i++) { cin >> a[i]; } Reform(); int ans = 0; for(int i = 1; i <= n; i++) { l[i] = get(id[i] - 1 , 0) + 1; ans = max(ans , l[i]); up(id[i] , l[i] , 0); } ms(bit , 0); for(int i = n; i >= 1; i--) { r[i] = get(id[i] + 1 , 1) + 1; up(id[i] , r[i] , 1); } ms(bit , 0); for(int i = n - 1; i >= 1; i--) { up(id[i + 1] , r[i + 1] , 1); int pos = upper_bound(all(P) , a[i] - x) - P.begin() + 1; ans = max(ans , l[i] + get(pos , 1)); } cout << ans; } /** **/ signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int tc; tc = 1; while(tc--) solve(); //execute; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:160:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:161:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...