제출 #293617

#제출 시각아이디문제언어결과실행 시간메모리
293617Dovran모임들 (IOI18_meetings)C++11
0 / 100
5600 ms1820 KiB
#include <bits/stdc++.h> #include "meetings.h" #define N 100009 #define LL 1000000009 #define pii pair <int, int> #define ff first #define ss second #define sz size #define pb push_back #define ll long long using namespace std; int n, v[N]; pii t[4*N]; void bld(int nd, int l, int r){ if(l==r){ t[nd].ff=v[l]; t[nd].ss=l; return; } int md=(l+r)/2; bld(nd*2, l, md); bld(nd*2+1, md+1, r); if(t[nd*2]<=t[nd*2+1]) t[nd].ss=t[nd*2].ss; else t[nd].ss=t[nd*2+1].ss; t[nd].ff=max(t[nd*2].ff, t[nd*2+1].ff); } pii tap(int nd, int l, int r, int x, int y){ if(l>=x and r<=y){ return t[nd]; } if(l>y or r<x){ return {0, 0}; } int md=(l+r)/2; return max(tap(nd*2, l, md, x, y), tap(nd*2+1, md+1, r, x, y)); } std::vector<ll> minimum_costs(std::vector<int>H, std::vector<int>L, std::vector<int>R){ n=H.sz(); for(int i=0; i<n; i++) v[i]=H[i]; bld(1, 0, n-1); vector<ll>e; for(int i=0; i<(int)L.size(); i++){ int l=L[i], r=R[i]; int bg=l, en=r; ll ans=0; while(r>=l){ int md=(l+r)/2; pii p=tap(1, 0, n-1, l, r); if(p.ss<md) r=md-1; else if(p.ss>md) l=md+1; else{ int a=tap(1, 0, n-1, l, md-1).ss; int b=tap(1, 0, n-1, md+1, r).ss; if(a>=b) l=md+1; else r=md-1; } } for(int j=bg; j<=en; j++) if(j<=l) ans+=tap(1, 0, n-1, j, l).ff; else ans+=tap(1, 0, n-1, l, j).ff; e.pb(ans); } return e; }
#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...