Submission #1241207

#TimeUsernameProblemLanguageResultExecution timeMemory
1241207phamducluongFinancial Report (JOI21_financial)C++20
19 / 100
148 ms11940 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; using ll=long long; //typedef tree<int,null_type,less_equal<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define mem(a,x) memset(a,x,sizeof(a)) #define fast(s) s.reserve(2000); s.max_load_factor(0.5); #define F first #define S second #define pii pair <int, int> #define all(p) p.begin(), p.end() template<typename T> bool maximum(T &A, const T &B) {return A<B? A=B, true: false;} template<typename T> bool minimum(T &A, const T &B) {return A>B? A=B, true: false;} template<typename T> T gcd(T t) {return t;} template<typename T, typename... Args> T gcd(T t, Args... args) {return __gcd(t,args...);}; void print(bool condition=1) {cout<<(condition? "YES\n": "NO\n");} const int mod=1e9+7; const int INF=1e9; const int div2=5e8+4; const int N=1e6+5, M=1e5; int n, d, a[N], mx[N], dp[N], res; vector<int> num; priority_queue<pii,vector<pii>,greater<pii>> q; void file() { #define task "main" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } struct SegmentTree { int n; vector<int> t; void init(int _n) { n=_n; t.resize(2*n+5,0); } void update(int p, int val) { for(t[p+=n]=val; p>1; p>>=1) t[p>>1]=max(t[p],t[p^1]); } int get(int l, int r) { int res=0; for(l+=n, r+=n+1; l<r; l>>=1, r>>=1) { if(l&1) maximum(res,t[l++]); if(r&1) maximum(res,t[--r]); } return res; } } st; void Solve() { cin>>n>>d; for(int i=1; i<=n; ++i) { cin>>a[i]; num.push_back(a[i]); } sort(all(num)); num.erase(unique(all(num)),num.end()); st.init((int)num.size()); for(int i=1; i<=n; ++i) a[i]=upper_bound(all(num),a[i])-num.begin(); for(int i=1; i<=n; ++i) { while(q.size()>1) { int u=q.top().S, du=q.top().F; q.pop(); int v=q.top().S, dv=q.top().F; if(i-u>d && (du!=dv || (du==dv && i-v>d))) { q.pop(); if(mx[a[u]]==u) st.update(du,0); } else { q.push({du,u}); break; } } dp[i]=st.get(1,a[i]-1)+1; maximum(res,dp[i]); st.update(a[i],dp[i]); mx[a[i]]=i; q.push({a[i],i}); } cout<<res; } signed main() { file(); Solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void file()':
Main.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         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...