제출 #868609

#제출 시각아이디문제언어결과실행 시간메모리
868609prohackerFinancial Report (JOI21_financial)C++14
53 / 100
278 ms42576 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double using namespace std; const int N = 3e5+10; const int INF = INT_MAX; const int mod = 1e9+7; int n,rmq[N][15]; int a[N],dp[N]; int D,lg[N]; multiset<int> s; pair<int,int> b[N]; void pre_calc() { for(int i = 1 ; i < D ; i++) { s.insert(a[i]); rmq[i][0] = mod; } for(int i = D ; i <= n ; i++) { s.insert(a[i]); rmq[i][0] = *s.begin(); s.erase(s.find(a[i-D+1])); } for(int j = 1 ; (1 << j) <= n ; j++) { for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) { rmq[i][j] = max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]); } } for(int i = 1 ; i <= n ; i++) { b[i] = {a[i],i}; } } int get(int u, int v) { int k = lg[v-u+1]; return max(rmq[u][k],rmq[v-(1<<k)+1][k]); } int Find(int st) { int l = st+D; int r = n; int res = n; while(l <= r) { int mid = l + r >> 1; if(get(st+D,mid) > a[st]) { res = mid; r = mid-1; } else { l = mid+1; } } return res; } int tree[4*N]; void update(int pos, int val, int id = 1, int l = 1, int r = n) { if(l == r) { tree[id] = max(tree[id],val); return; } int mid = l + r >> 1; if(pos <= mid) { update(pos,val,id << 1,l,mid); } else { update(pos,val,id << 1 | 1,mid+1,r); } tree[id] = max(tree[id << 1],tree[id << 1 | 1]); } int get_dp(int u, int v, int id = 1, int l = 1, int r = n) { if(v < l or r < u) { return 0; } if(u <= l and r <= v) { return tree[id]; } int mid = l + r >> 1; return max(get_dp(u,v,id << 1,l,mid),get_dp(u,v,id << 1 | 1,mid+1,r)); } signed main() { if (fopen("financial.inp", "r")) { freopen("financial.inp", "r", stdin); freopen("financial.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> D; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; } for(int i = 1 ; i <= n ; i++) { lg[i] = __lg(i); } pre_calc(); sort(b+1,b+n+1,[](pair<int,int> u, pair<int,int> v) { if(u.first != v.first) { return u.first > v.first; } return u.second < v.second; }); for(int i = 1 ; i <= n ; i++) { update(b[i].second,get_dp(b[i].second+1,Find(b[i].second))+1); } cout << tree[1]; return 0; }

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

Main.cpp: In function 'void pre_calc()':
Main.cpp:29:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |             rmq[i][j] = max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                                   ~^~
Main.cpp: In function 'int Find(int)':
Main.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int get_dp(int, int, int, int, int)':
Main.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("financial.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("financial.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...