제출 #999512

#제출 시각아이디문제언어결과실행 시간메모리
999512snpmrnhlol별자리 3 (JOI20_constellation3)C++17
35 / 100
1506 ms155732 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 2e5; const ll G = 2*N; const ll logN = 20; ll n,m; vector <ll> e[G]; ll v[N]; vector <ll> lefte[N + 1]; vector <ll> righte[N + 1]; ll prleft[N + 1][logN],prright[N + 1][logN]; ll subleft[N + 1],subright[N + 1]; ll leftside[N + 1],rightside[N + 1]; ///bear your fangs its time to fight ///pa pa pa parade in shame tonight ll ordleft[N + 1],ordright[N + 1]; ll ord2left[N + 1],ord2right[N + 1]; ll cntleft = 0,cntright = 0; ll leftid[N],rightid[N]; ll fenleft[N + 1],fenright[N + 1]; /// ll stk[N]; vector <ll> p; struct star{ ll x,y,c; }v2[N]; vector <ll> cand[G]; map<ll,pair<ll,ll>> f; vector <ll> points; ll dp[G]; ll fuckleft[N],fuckright[N]; ll cnt = 0; void addedge(ll u,ll w){ e[u].push_back(w); } void addleft(ll pos,ll nr){ for(ll i = pos;i <= n;i|=(i + 1)){ fenleft[i]+=nr; } } void addright(ll pos,ll nr){ for(ll i = pos;i <= n;i|=(i + 1)){ fenright[i]+=nr; } } ll getleft(ll pos){ ll r = 0; for(ll i = pos;i >= 0;i&=(i + 1),i--){ r+=fenleft[i]; } return r; } ll getright(ll pos){ ll r = 0; for(ll i = pos;i >= 0;i&=(i + 1),i--){ r+=fenright[i]; } return r; } void dfs(ll node){ ll mx = 0; for(auto i:e[node]){ dfs(i); mx+=dp[i]; } for(auto i:cand[node]){ ///leftadd star s = v2[i]; ll candcost = s.c; ll j = s.x; candcost+=getright(ordright[j]); while(j != n && v[j] < s.y){j = rightside[j];}; candcost-=getright(ordright[j]); j = s.x; candcost+=getleft(ordleft[j]); while(j != n && v[j] < s.y){j = leftside[j];}; candcost-=getleft(ordleft[j]); mx = max(mx,candcost); } dp[node] = mx; if(ord2left[node] != -1){ fuckleft[ord2left[node]]+=dp[node]; addleft(ordleft[ord2left[node]],dp[node]); addleft(ordleft[ord2left[node]] + subleft[ord2left[node]],-dp[node]); } if(ord2right[node] != -1){ fuckright[ord2right[node]]+=dp[node]; addright(ordright[ord2right[node]],dp[node]); addright(ordright[ord2right[node]] + subright[ord2right[node]],-dp[node]); } } void dfsleft(ll node, ll p){ prleft[node][0] = p; subleft[node] = 1; ordleft[node] = cntleft++; for(auto i:lefte[node]){ dfsleft(i, node); subleft[node]+=subleft[i]; } } void dfsright(ll node, ll p){ prright[node][0] = p; subright[node] = 1; ordright[node] = cntright++; for(auto i:righte[node]){ dfsright(i, node); subright[node]+=subright[i]; } } int main(){ cin>>n; p.resize(n); for(ll i = 0;i < n;i++){ cin>>v[i]; p[i] = i; leftid[i] = rightid[i] = -1; } sort(p.begin(),p.end(),[&](ll a,ll b){ if(v[a] == v[b])return a < b; return v[a] > v[b]; }); cin>>m; ll sum = 0; for(ll i = 0;i < m;i++){ cin>>v2[i].x>>v2[i].y>>v2[i].c; sum+=v2[i].c; v2[i].x--; } sort(v2,v2 + m,[&](star a,star b){ return a.y > b.y; }); f[0] = {n - 1,cnt++}; ll pt = 0; ll pt2 = 0; for(ll i = n;i >= 1;i--){ points.clear(); while(pt2 < n && v[p[pt2]] >= i){ points.push_back(p[pt2]); pt2++; } ll j = 0; while(j < points.size()){ auto it = prev(f.upper_bound(points[j])); ll k = j; while(k < points.size() && points[k] <= it->second.first){ k++; } ll l = it->first; ll r = it->second.first; ll id = it->second.second; f.erase(it); for(ll p = j;p <= k;p++){ ll lside = (p == j?l:points[p - 1] + 1); ll rside = (p == k?r:points[p] - 1); if(lside <= rside){ addedge(id,cnt); f[lside] = {rside,cnt}; ord2left[cnt] = ord2right[cnt] = -1; if(p != k){ leftid[rside + 1] = cnt; ord2left[cnt] = rside + 1; } if(p != j){ rightid[lside - 1] = cnt; ord2right[cnt] = lside - 1; } cnt++; } } j = k; } while(pt < m && v2[pt].y >= i){ ll id = prev(f.upper_bound(v2[pt].x))->second.second; cand[id].push_back(pt); pt++; } } ll cnt2 = 0; for(ll i = 0;i < n;i++){ while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){ cnt2--; } leftside[i] = (cnt2 == 0?n:stk[cnt2 - 1]); lefte[leftside[i]].push_back(i); stk[cnt2++] = i; } cnt2 = 0; for(ll i = n - 1;i >= 0;i--){ while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){ cnt2--; } rightside[i] = (cnt2 == 0?n:stk[cnt2 - 1]); righte[rightside[i]].push_back(i); stk[cnt2++] = i; } dfsleft(n, -1); dfsright(n, -1); for(ll j = 1;j < logN;j++){ for(ll i = 0;i <= n;i++){ prleft[i][j] = prleft[prleft[i][j - 1]][j - 1]; prright[i][j] = prright[prright[i][j - 1]][j - 1]; } } dfs(0); cout<<sum - dp[0]; return 0; }

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

constellation3.cpp: In function 'int main()':
constellation3.cpp:144:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         while(j < points.size()){
      |               ~~^~~~~~~~~~~~~~~
constellation3.cpp:147:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             while(k < points.size() && points[k] <= it->second.first){
      |                   ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...