| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1095758 | guagua0407 | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#include "meetings.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int B=400;
const int mxn=1e5+5;
const ll inf=1e18;
int n;
vector<vector<int>> lst,rst;
vector<int> h;
int L=0,R=0;
vector<ll> segtree,lazy;
void push(int v){
if(lazy[v]==0) return;
segtree[v*2]+=lazy[v];
segtree[v*2+1]+=lazy[v];
lazy[v*2]+=lazy[v];
lazy[v*2+1]+=lazy[v];
lazy[v]=0;
}
void update(int tl,int tr,ll val,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return;
}
if(tl<=l and r<=tr){
segtree[v]+=val;
lazy[v]+=val;
return;
}
int mid=(l+r)/2;
push(v);
update(tl,min(mid,tr),val,l,mid,v*2);
update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
segtree[v]=min(segtree[v*2],segtree[v*2+1]);
}
ll query(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return inf;
}
if(tl<=l and r<=tr){
return segtree[v];
}
int mid=(l+r)/2;
push(v);
return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
void updl(int l,int d){
//update(l,l,1ll*(-inf)*d);
int pos=(int)rst[l].size()-1;
while(pos>=0 and rst[l][pos]<=R){
int r=(pos>=1?rst[l][pos-1]:mxn);
r=min(r,R+1);
update(l,l,1ll*h[rst[l][pos]]*(r-rst[l][pos])*d);
update(max(l+1,rst[l][pos]),r-1,1ll*h[rst[l][pos]]*d);
pos--;
}
}
void updr(int r,int d){
//update(r,r,1ll*(-inf)*d);
int pos=(int)lst[r].size()-1;
while(pos>=0 and lst[r][pos]>=L){
int l=(pos>=1?lst[r][pos-1]:-1);
l=max(l,L-1);
update(r,r,1ll*h[lst[r][pos]]*(lst[r][pos]-l)*d);
update(l+1,min(r-1,lst[r][pos]),1ll*h[lst[r][pos]]*d);
pos--;
}
}
void sir(int l,int r){
while(L>l){
L--;
updl(L,1);
}
while(R<r){
R++;
updr(R,1);
}
while(L<l){
updl(L,-1);
L++;
}
while(R>r){
updr(R,-1);
R--;
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
h=H;
n=(int)H.size();
lst.resize(n);
rst.resize(n);
segtree=vector<ll>(4*n);
lazy=vector<ll>(4*n);
{
vector<int> st;
for(int i=0;i<n;i++){
while(!st.empty() and h[i]>=h[st.back()]){
st.pop_back();
}
st.push_back(i);
lst[i]=st;
}
}
{
vector<int> st;
for(int i=n-1;i>=0;i--){
while(!st.empty() and h[i]>=h[st.back()]){
st.pop_back();
}
st.push_back(i);
rst[i]=st;
}
}
int q=(int)L.size();
vector<vector<pair<int,int>>> qs(B);
for(int i=0;i<q;i++){
qs[L[i]/B].push_back({R[i],i});
}
update(0,0,h[0]);
//update(1,n-1,inf);
vector<ll> ans(q);
bool tf=false;
for(int i=0;i<B;i++){
if(qs[i].empty()) continue;
if(!tf) sort(all(qs[i]));
else sort(qs[i].rbegin(),qs[i].rend());
tf=!tf;
for(auto v:qs[i]){
int id=v.s;
sir(L[id],R[id]);
ans[id]=query(L[id],R[id]);
}
}
return ans;
}
/*
4 2
2 4 3 5
0 2
1 3
*/