| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 784263 | APROHACK | 모임들 (IOI18_meetings) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ss second
#define ff first
#define izquierda 0
#define derecha 1
using namespace std;
ll n, q;
ll nxtGrande[100001];
ll anteriorGrande[100001];
ll dp[100001][2];
vector<int>height;
struct segTree{
int dd, ht;
ll maximo;
ll donde;
int mid;
segTree *L, *R;
segTree(int l, int r){
dd = l;
ht = r;
mid = (dd + ht)/2;
maximo = -1;
donde = 0;
if(l!=r){
L = new segTree(l, mid);
R = new segTree(mid+1, r);
if(L->maximo > R->maximo){
maximo = L->maximo;
donde = L->donde;
}else{
maximo = R->maximo;
donde = R->donde;
}
}else{
maximo = height[l];
donde = l;
}
}
ll getMax(int l , int r){
if( dd == l and r == ht){
return maximo;
}
if( r <= mid ) return L->getMax(l, r);
if( mid < l) return R->getMax(l, r);
return max(L->getMax(l, mid), R->getMax(mid+1, r));
}
pair<ll, ll> query(int l, int r){
if( dd == l and r == ht){
return {donde, maximo};
}
if( r <= mid ) return L->query(l, r);
if( mid < l) return R->query(l, r);
pair<ll, ll> a = L->query(l, mid);
pair<ll, ll> b = R->query(mid+1, r);
if(a.ss > b.ss){
return a;
}else{
return b;
}
}
};
struct seg1{
int dd, ht;
ll maximo;
int mid;
segTree *L, *R;
segTree(int l, int r){
dd = l;
ht = r;
mid = (dd + ht)/2;
maximo = -1;
if(l!=r){
L = new segTree(l, mid);
R = new segTree(mid+1, r);
if(L->maximo > R->maximo){
maximo = L->maximo;
}else{
maximo = R->maximo;
}
}else{
maximo = -1;
}
}
void update(int pos, ll cuanto){
if(dd == ht)maximo = max(maximo, cuanto);
else if(pos <= mid)L->update(pos, cuanto);
else R->update(pos, cuanto);
}
ll query(int l, int r){
if( dd == l and r == ht){
return maximo;
}
if( r <= mid ) return L->query(l, r);
if( mid < l) return R->query(l, r);
ll a = L->query(l, mid);
ll b = R->query(mid+1, r);
return max(L->query(l, mid), R->query(mid+1, r));
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
q = L.size();
n = H.size();
height = H;
set<pair<ll, int> >alturas; // alturas y indices.
for(int i = n-1 ; i >= 0 ; i --){
auto sig = alturas.upper_bound({H[i], n});
if(sig == alturas.end())nxtGrande[i] = -1;
else{
nxtGrande[i] = (*sig).ss;
}
vector<pair<ll, int>>toE;
for(auto j : alturas){
if(j.ff > H[i])break;
toE.pb(j);
}
for(auto j : toE)alturas.erase(j);
alturas.insert({H[i], i});
}
alturas.clear();
for(int i = 0 ; i < n ; i ++){
auto sig = alturas.upper_bound({H[i], n});
if(sig == alturas.end())anteriorGrande[i] = -1;
else anteriorGrande[i] = (*sig).ss;
vector<pair<ll, int>>toE;
for(auto j : alturas){
if(j.ff > H[i])break;
toE.pb(j);
}
for(auto j : toE)alturas.erase(j);
alturas.insert({H[i], i});
}
//for(int i = 0 ; i < n ; i++)cout << anteriorGrande[i] << " " ;
//for(int i = 0 ; i < n ; i ++)cout << nxtGrande[i] << " ";
for(ll i = n-1 ; i >= 0 ; i --){
int sig = nxtGrande[i];
if(sig == -1)dp[i][derecha] = (n-i)*H[i];
else{
dp[i][derecha] = (sig-i)*H[i] + dp[sig][derecha];
}
}
for(ll i = 0 ; i < n ; i ++){
int sig = anteriorGrande[i];
if(sig == -1)dp[i][izquierda] = (i+1)*H[i];
else{
dp[i][izquierda] = (i-sig)*H[i] + dp[sig][izquierda];
}
}
bool all2 = true;
for(int i = 0 ; i < n ; i ++)if(H[i] != 1 and H[i] != 2)all2 = false;
if(!all2){
//for(int i = 0 ; i < n ; i ++)cout << dp[i][derecha] << " " ;
//for(int i = 0 ; i < n ; i ++)cout << dp[i][izquierda] << " " ;
segTree *st = new segTree(0, n-1);
vector<ll>C;
for(int query = 0 ; query < q; query ++){
ll minimum = LLONG_MAX;
//cout << "q = " << query << endl;
for(int i = L[query] ; i <= R[query] ; i ++){
ll k = st->query(i, R[query]).ff;
ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k];
k = st->query(L[query], i).ff;
ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k];
minimum = min(minimum, der + izq - H[i]);
//cout << i << " " << izq << " + " << der << endl;
}
C.pb(minimum);
}
}else{
seg1 *stR = new seg1(0, n-1);
int lleva = 0, desde = -1;
vector<pair<int, int>>conjuntitos;
int pertenece[n+1];
for(int i = 0 ; i < n ; i ++){
if(H[i] == 2 and desde == -1)continue;
if(H[i] == 2){
conjuntitos.pb(desde, i-1);
for(int j = desde ; j <= i-1 ; j ++)pertenece[j] = conjuntitos.size()-1;
desde = -1;
lleva = 0;
stR->update(i-1, lleva);
}else{
if(desde == -1){
lleva = 1;
desde = i;
}else lleva ++ ;
}
}
for(int query = 0 ; query < q ; query ++){
ll li = L[query], ls = R[query];
ll total = R[query] - L[query] + 1;
ll a = 0, b = 0;
if(H[li] == 1){
a = conjuntitos[pertenece[li]].ss - L[query] + 1;
li = conjuntitos[pertenece[li]].ss + 1
}
if(H[ls] == 1){
b = R[query]-conjuntitos[pertenece[ls]].ff + 1;
ls = conjuntitos[pertenece[ls]].ff -1;
}
ll ans ;
ans = min ( ans, (total-a)*2 + a);
ans = min(ans, (total - b)*2 + b);
if(li <= ls){
ll cu = st->query(li, ls);
ans = min (ans, (total - cu)*2 + cu;
}
C.pb(ans);
}
}
return C;
}