#pragma GCC optimize("Ofast")
#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 int inf=1e9;
int n;
vector<vector<int>> lst,rst;
vector<int> h;
int L=0,R=0;
vector<int> 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,int 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]);
}
int 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){
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,h[rst[l][pos]]*(r-rst[l][pos])*d);
update(max(l+1,rst[l][pos]),r-1,h[rst[l][pos]]*d);
pos--;
}
}
void updr(int r,int 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,h[lst[r][pos]]*(lst[r][pos]-l)*d);
update(l+1,min(r-1,lst[r][pos]),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<int>(4*n);
lazy=vector<int>(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]);
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2602 ms |
3396 KB |
Output is correct |
| 3 |
Execution timed out |
5554 ms |
19280 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2602 ms |
3396 KB |
Output is correct |
| 3 |
Execution timed out |
5554 ms |
19280 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
