제출 #680992

#제출 시각아이디문제언어결과실행 시간메모리
680992arnold518Financial Report (JOI21_financial)C++17
0 / 100
4059 ms17232 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 3e5; const int INF = 1e9+7; int N, D; int A[MAXN+10], P[MAXN+10]; struct UF { int par[MAXN+10]; int Find(int x) { if(x==par[x]) return x; return Find(par[x]); } void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; } }uf; struct SEG { int tree[MAXN*4+10]; SEG() { fill(tree, tree+MAXN*4+10, -INF); } void update(int node, int tl, int tr, int p, int q) { tree[node]=max(tree[node], q); if(tl==tr) return; int mid=tl+tr>>1; if(p<=mid) update(node*2, tl, mid ,p, q); else update(node*2+1, mid+1, tr, p, q); } int query(int node, int tl, int tr, int l, int r) { if(l<=tl && tr<=r) return tree[node]; if(r<tl || tr<l) return -INF; int mid=tl+tr>>1; return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r)); } }seg; struct SEG2 { pii tree[MAXN*4+10]; void init(int node, int tl, int tr) { if(tl==tr) { tree[node]={A[tl], tl}; return; } int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); } pii query(int node, int tl, int tr, int l, int r) { if(l<=tl && tr<=r) return tree[node]; if(r<tl || tr<l) return pii(INF, INF); int mid=tl+tr>>1; return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r)); } }seg2; int dp[MAXN+10]; int main() { scanf("%d%d", &N, &D); for(int i=1; i<=N; i++) scanf("%d", &A[i]); seg2.init(1, 1, N); vector<int> V; for(int i=1; i<=N; i++) V.push_back(i); sort(V.begin(), V.end(), [&](const int &p, const int &q) { if(A[p]==A[q]) return p>q; return A[p]<A[q]; }); for(int i=1; i<=N; i++) uf.par[i]=i; for(auto it : V) { pii t=seg2.query(1, 1, N, it+1, it+D); if(t.first<=A[it]) uf.Union(t.second, it); t=seg2.query(1, 1, N, it-D, it-1); if(t.first<=A[it]) uf.Union(t.second, it); P[it]=uf.Find(it); } int ans=1; sort(V.begin(), V.end(), [&](const int &p, const int &q) { if(A[p]==A[q]) return p<q; return A[p]>A[q]; }); for(auto it : V) { dp[it]=seg.query(1, 1, N, it, P[it]+D)+1; if(P[it]==N) dp[it]=max(dp[it], 1); seg.update(1, 1, N, it, dp[it]); ans=max(ans, dp[it]); } printf("%d\n", ans); }

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

Main.cpp: In member function 'void SEG::update(int, int, int, int, int)':
Main.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'int SEG::query(int, int, int, int, int)':
Main.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG2::init(int, int, int)':
Main.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'pii SEG2::query(int, int, int, int, int)':
Main.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d", &N, &D);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
#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...