제출 #425033

#제출 시각아이디문제언어결과실행 시간메모리
425033Pbezz모임들 (IOI18_meetings)C++14
0 / 100
402 ms786436 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back typedef pair<ll,ll> pii; const ll MAXN = 5005; const ll INF = 1e16+7; ll dp[MAXN],seg[4*MAXN],n; //seg[node]=min index que maximiza dp[index] void recalculate(ll node){ // cout<<node<<" "<<seg[2*node+1]<<" "<<seg[2*node+2]<<endl; if(dp[seg[2*node+1]]>=dp[seg[2*node+2]]){ seg[node]=seg[2*node+1]; }else if(dp[seg[2*node+1]]<dp[seg[2*node+2]]){ seg[node]=seg[2*node+2]; } } void build(ll node, ll left, ll right){ if(left==right){ seg[node]=left; }else{ ll middle = (left+right)/2; build(2*node+1,left,middle); build(2*node+2,middle+1,right); recalculate(node); } } ll querie(ll node, ll left, ll right, ll a, ll b){ if(a<=left&&b>=right){ return seg[node]; } ll middle = (left+right)/2,k1=n+1,k2=n+1; if(a<=middle)k1=querie(2*node+1,left,middle,a,b); if(b>=middle+1)k2=querie(2*node+2,middle+1,right,a,b); if(a<=middle && dp[k1]>=dp[k2])return k1; return k2; } std::vector<long long> minimum_costs(std::vector<int>H,std::vector<int>L, std::vector<int> R) { int Q = L.size(),i,k,bruh; n=(ll)H.size(); dp[n+1]=0; for(i=n;i>=1;i--){ if(H[i-1]==2){ dp[i]=0; continue; } dp[i]=dp[i+1]+1; } build(0,1,n); // for(i=1;i<=n;i++){ //cout<<i<<" "<<seg[i]<<endl; //} std::vector<long long> C(Q); for(i=0;i<Q;i++){ k = querie(0,1,n,L[i],R[i]); if(k+dp[k]-1<=R[i]){ C[i]=dp[k]+2*(R[i]-L[i]+1-dp[k]); continue; } C[i] = R[i]-k+1; if(k>L[i]){ bruh = querie(0,1,n,L[i],k-1); C[i] = max(C[i],dp[bruh]); } C[i] = C[i]+2*(R[i]-L[i]+1-C[i]); } return C; }
#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...