제출 #1127742

#제출 시각아이디문제언어결과실행 시간메모리
1127742Haciyev12Global Warming (CEOI18_glo)C++20
10 / 100
121 ms9812 KiB
/*********************************** ██╗░░██╗████████╗██╗░░░░░███╗░░░███╗ ██║░░██║╚══██╔══╝██║░░░░░████╗░████║ ███████║░░░██║░░░██║░░░░░██╔████╔██║ ██╔══██║░░░██║░░░██║░░░░░██║╚██╔╝██║ ██║░░██║░░░██║░░░███████╗██║░╚═╝░██║ ╚═╝░░╚═╝░░░╚═╝░░░╚══════╝╚═╝░░░░░╚═╝ ***********************************/ //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <unistd.h> //#include "functions.h" #define int l #define f first #define s second #define endl '\n' #define l long long #define ara <<" "<< #define pb push_back #define pairs pair<l,l> #define NO cout<<"NO"<<endl #define stop system("pause") #define YES cout<<"YES"<<endl #define all(v) v.begin(),v.end() #define yesno(v) ((v) ? "YES" : "NO") #define dbg(x) cout<<#x<<" = "<<x<<endl; #define filereader() ifstream cin(input); #define fileprinter() ofstream cout(output); #define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL); using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int> , rb_tree_tag, tree_order_statistics_node_update> indexed_set; const l N = 2e5 + 5; const l INF = 1e18; const l mod = 1e9 + 7; const string input = "input.txt"; const string output = "output.txt"; l gcd(l a, l b){ if(b == 0){ return a; } return gcd(b,a%b); } l binpow(l a, l b) { if (b == 0) return 1; l res = binpow(a, b / 2); if (b % 2) return ((res * res) % mod * a) % mod; else return (res * res) % mod; } void solve() { l n, x; cin >> n >> x; vector<l> v(n); vector<l> used(n, 0), par(n, 0); set<l> s; for (l &i : v) { cin >> i; } s.insert(v[n - 1]); for (l i = n - 2; i >= 0; i--) { if (!s.empty()) { l bg = *s.begin(); if (v[i] < bg) { used[i] = 1; s.insert(v[i]); } else { auto t = s.upper_bound(v[i]); if (t != s.begin()) { t--; par[i] = *t; s.erase(t); s.insert(v[i]); } } } } l maks = s.size(); set<l> st; for (l i = 0; i < n; i++) { if (!s.empty()) { s.erase(v[i]); } if (used[i] == 0) { s.insert(par[i]); } l lst = -INF; if (!st.empty()) { lst = *st.rbegin(); } v[i] -= x; if (v[i] <= lst && st.find(v[i]) != st.end()) { st.erase(st.lower_bound(v[i])); } st.insert(v[i]); while (!st.empty() && !s.empty() && *st.rbegin() >= *s.begin()) { auto p = st.end(); p--; st.erase(p); } l sz = st.size() + s.size(); maks = max(maks, sz); } cout << maks << endl; } signed main(){ //fast; l n = 1; //cin>>n; while(n--){ solve(); } }
#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...