제출 #570943

#제출 시각아이디문제언어결과실행 시간메모리
570943dantoh000Financial Report (JOI21_financial)C++14
5 / 100
789 ms72316 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int,int> ii; int n,d; int a[300005]; int p[300005]; int l[300005]; int r[300005]; int ans[300005]; int ANS; void init(int n){ for (int i = 0; i < n; i++){ p[i] = l[i] = r[i] = i; } } int find(int x){ return p[x] == x ? x : p[x] = find(p[x]); } void un(int x, int y){ x = find(x), y = find(y); if (x == y) return; p[y] = x; l[y] = min(l[y], l[x]); r[y] = max(r[y], r[x]); } struct node{ int s,e,m,v; node *l, *r; node (int _s, int _e){ s = _s, e = _e; m = (s+e)/2; if (s != e){ l = new node(s,m); r = new node(m+1,e); } } void up(int x, int nv){ if (s == e){ v = nv; return;} if (x > m) r->up(x,nv); else l->up(x,nv); v = max(l->v,r->v); } int qu(int qs, int qe){ ///printf("%d %d %d %d\n",s,e,qs,qe); if (qs ==s && qe ==e ) return v; if (qs > m) return r->qu(qs,qe); else if (qe <= m) return l->qu(qs,qe); else return max(l->qu(qs,m), r->qu(m+1,qe)); } } *root; vector<ii> v; bool cmp(ii a, ii b){ if (a.fi != b.fi) return a.fi < b.fi; else return a.se > b.se; } int main(){ scanf("%d%d",&n,&d); v.resize(n); for (int i = 0; i < n; i++) { scanf("%d",&v[i].fi); v[i].se = i; } sort(v.begin(),v.end(),cmp); set<int> s; init(n); root = new node(0,n); for (int i = 0; i < n; i++){ int ID = v[i].se; auto it = s.lower_bound(ID); if (it != s.end() && *it-ID <= d){ un(*it, ID); } if (it != s.begin() && ID-*prev(it) <= d){ un(*prev(it), ID); } s.insert(ID); int L = l[find(ID)]; //printf("%d %d\n",ID,L); ans[ID] = root->qu(max(0,L-d), ID) + 1; //printf("ans %d\n",ans[ID]); root->up(ID, ans[ID]); ANS = max(ANS,ans[ID]); } printf("%d\n",ANS); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d",&v[i].fi);
      |         ~~~~~^~~~~~~~~~~~~~~
#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...