제출 #380672

#제출 시각아이디문제언어결과실행 시간메모리
380672sad모임들 (IOI18_meetings)C++14
4 / 100
5567 ms2480 KiB
#include "meetings.h" #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back using namespace std; ll n;vector<ll >ans; const ll N=5090; ll tree[N*4],pa[N],lef[N]; vector<ll>vv,h,w; vector<ll>v;ll c=0; void up(int ind,int st,int end,int uind,int x) { if(uind>end||uind<st)return; if(st==end) { tree[ind]=x; return; } int m=(st+end)/2; up(ind*2+1,st,m,uind,x); up(ind*2+2,m+1,end,uind,x); tree[ind]=tree[ind*2+1]+tree[ind*2+2]; } ll get (int ind,int st,int end,int l,int r) { if(l>end||r<st)return 0; if(l<=st&&end<=r)return tree[ind]; ll m=(st+end)/2; return (get(ind*2+1,st,m,l,r)+get(ind*2+2,m+1,end,l,r)); } ll solve(int l,int r) { v.clear(); ll mn=1e17; ll re=0; for(ll i=l;i<r+1;i++) { ll r=0; int x=v.size();x--; while(x>=0&&v[x]<=h[i]) { ll cnt=get(0,0,c-1,v[x],v[x]); up(0,0,c-1,v[x],0); re-=cnt*pa[v[x]]; r+=cnt;x--; } r++; v.pb(h[i]); re+=r*pa[h[i]]; lef[i]=re; up(0,0,c-1,h[i],r); } v.clear(); memset(tree,0,sizeof tree); re=0; for(ll i=r;i>l-1;i--) { ll r=0; int x=v.size();x--; while(x>=0&&v[x]<=h[i]) { ll cnt=get(0,0,c-1,v[x],v[x]); up(0,0,c-1,v[x],0); re-=cnt*pa[v[x]]; r+=cnt; x--; } r++; v.pb(h[i]); re+=r*pa[h[i]]; mn=min(mn,lef[i]+re-pa[h[i]]); up(0,0,c-1,h[i],r); } memset(tree,0,sizeof tree); memset(lef,0,sizeof lef); return mn; } vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) { ans.clear(); vv.clear(); n=H.size(); for(ll i=0;i<n;i++){ w.pb(H[i]); } sort(w.begin(),w.end()); w.pb(-1); for(ll i=1;i<w.size();i++) { if(w[i]!=w[i-1])vv.pb(w[i-1]); } for(ll i=0;i<n;i++) { ll x=lower_bound(vv.begin(),vv.end(),H[i])-vv.begin(); h.pb(x); pa[x]=H[i]; } c=vv.size(); ll q=L.size(); for(ll j=0;j<q;j++) { ans.pb(solve(L[j],R[j])); } return ans; } /* 4 2 2 4 3 5 0 2 1 3 */

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

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:90:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i=1;i<w.size();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...