Submission #1108387

#TimeUsernameProblemLanguageResultExecution timeMemory
1108387koukirocksGlobal Warming (CEOI18_glo)C++17
17 / 100
38 ms4808 KiB
#include <bits/stdc++.h> #define speed ios_base::sync_with_stdio(0); cin.tie(0) #define all(x) (x).begin(),(x).end() #define F first #define S second //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx,avx2") //#pragma GCC target("popcnt") using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll MAX=2e5+10,P=1e9+7; const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f; const ldb eps=1e-6; const ldb PI=acos(-1.0); const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; template<typename T> using vvector = vector<vector<T>>; map<pii,vector<int>> dp; void f(int n,int mx) { if (dp.find({n,mx})!=dp.end()) return; vector<int> &now = dp[{n,mx}]; now={}; for (int i=2;i<=min(mx,(int)sqrt(n));i++) { if (n%i==0) { f(n/i,i); for (int j:dp[{n/i,i}]) now.push_back(j+i-1); if (i*i!=n) { int ni=n/i; if (ni>mx) continue; f(n/ni,ni); for (int j:dp[{n/ni,ni}]) now.push_back(j+ni-1); } } } if (n<=mx) now.push_back(n-1); sort(all(now)); now.resize(unique(all(now))-now.begin()); // cout<<n<<" "<<mx<<" n mx\n"; // for (int i:now) cout<<i<<" "; // cout<<"\n"; } int main() { speed; int n,x; cin>>n>>x; vector<int> a(n+1); vector<int> dp(n+1); for (int i=1;i<=n;i++) { cin>>a[i]; } vector<int> curr; for (int i=1;i<=n;i++) { if (curr.empty() or curr.back()<a[i]) { curr.push_back(a[i]); } else { auto it = lower_bound(all(curr),a[i]); *it = a[i]; } dp[i]=curr.size(); // cout<<dp[i]<<" "; } // cout<<"dp\n"; curr.clear(); vector<int> dp2(n+1); for (int i=n;i>=1;i--) { if (curr.empty() or curr.back()>a[i]-x) dp2[i]=curr.size()+1; else dp2[i]=curr.size(); if (curr.empty() or curr.back()>a[i]) curr.push_back(a[i]); else { int l=0,r=curr.size()-1; while (l<r) { int mid=l+r>>1; if (curr[mid]<=a[i]) r=mid; else l=mid+1; } curr[l]=a[i]; } // cout<<dp2[i]<<" "; } // cout<<"dp2\n"; int ans=0; for (int i=1;i<=n;i++) { ans=max(ans,dp[i]+dp2[i]-1); } cout<<ans<<"\n"; return 0; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:81:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |                 int mid=l+r>>1;
      |                         ~^~
#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...