제출 #511037

#제출 시각아이디문제언어결과실행 시간메모리
511037CodeTiger927휴가 (IOI14_holiday)C++14
47 / 100
5063 ms51280 KiB
using namespace std; #include <iostream> #include <vector> #include <algorithm> #define MAXN 100005 pair<long long,int> add(pair<long long,int> a,pair<long long,int> b) { if(a.first == 0) return b; if(b.first == 0) return a; return make_pair(a.first + b.first,a.second + b.second); } int cnt; struct node { int lp,rp; pair<long long,int> v; } nodes[20 * MAXN]; int build_node(int l,int r) { int owo = cnt; node& uwu = nodes[cnt++] = node{-1,-1,{0,0}}; if(l == r) return owo; int m = (l + r) >> 1; uwu.lp = build_node(l,m); uwu.rp = build_node(m + 1,r); return owo; } int get_node(int lp,int rp) { int owo = cnt; node& uwu = nodes[cnt++] = node{lp,rp,add(nodes[lp].v,nodes[rp].v)}; return owo; } int get_node(pair<long long,int> v) { int owo = cnt; node& uwu = nodes[cnt++] = node{-1,-1,v}; return owo; } int upd(int p,int l,int r,int x,pair<long long,int> d) { node& uwu = nodes[p]; if(l == r) return get_node(add(uwu.v,d)); int m = (l + r) >> 1; if(x <= m) return get_node(upd(uwu.lp,l,m,x,d),uwu.rp); return get_node(uwu.lp,upd(uwu.rp,m + 1,r,x,d)); } pair<long long,int> get(int p,int l,int r,int a,int b) { node& uwu = nodes[p]; if(a > r || b < l) return make_pair(0,0); if(a <= l && b >= r) return uwu.v; int m = (l + r) >> 1; return add(get(uwu.lp,l,m,a,b),get(uwu.rp,m + 1,r,a,b)); } int st[MAXN]; int N,S,D; pair<long long,int> dp[MAXN]; void solve1(int x,int y,int a,int b) { if(x > y) return; int z = (x + y) >> 1; dp[z] = {-1,-1}; for(int i = a;i <= b;++i) { int l = 0; int r = N; while(l < r) { int m = (l + r + 1) >> 1; if(get(st[m],0,N - 1,z,i).second + (S - z) + (i - z) <= D) { l = m; }else{ r = m - 1; } } dp[z] = max(dp[z],{get(st[l],0,N - 1,z,i).first,-i}); } if(x == y) return; solve1(x,z - 1,a,-dp[z].second); solve1(z + 1,y,-dp[z].second,b); } void solve2(int x,int y,int a,int b) { if(x > y) return; int z = (x + y) >> 1; if(!dp[z].first) dp[z] = {-1,-1}; for(int i = a;i <= b;++i) { int l = 0; int r = N; while(l < r) { int m = (l + r + 1) >> 1; if(get(st[m],0,N - 1,i,z).second + (z - S) + (z - i) <= D) { l = m; }else{ r = m - 1; } } dp[z] = max(dp[z],{get(st[l],0,N - 1,i,z).first,i}); } if(x == y) return; solve2(x,z - 1,a,dp[z].second); solve2(z + 1,y,dp[z].second,b); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { N = n; S = start; D = d; vector<pair<long long,int>> v; for(int i = 0;i < N;++i) { v.push_back({-attraction[i],i}); } st[0] = build_node(0,N - 1); sort(v.begin(),v.end()); for(int i = 0;i < N;++i) { st[i + 1] = upd(st[i],0,N - 1,v[i].second,make_pair(-v[i].first,1)); } solve1(0,S,S,N - 1); solve2(S,N - 1,0,S); long long ans = 0; for(int i = 0;i < N;++i) { ans = max(ans,dp[i].first); } return ans; }

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

holiday.cpp: In function 'int get_node(int, int)':
holiday.cpp:34:8: warning: unused variable 'uwu' [-Wunused-variable]
   34 |  node& uwu = nodes[cnt++] = node{lp,rp,add(nodes[lp].v,nodes[rp].v)};
      |        ^~~
holiday.cpp: In function 'int get_node(std::pair<long long int, int>)':
holiday.cpp:40:8: warning: unused variable 'uwu' [-Wunused-variable]
   40 |  node& uwu = nodes[cnt++] = node{-1,-1,v};
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...