#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
int n;
long long ml[N],mr[N];
vector<int> a;
struct node
{
int pre,suf,mxa,all;
friend node operator+(const node &a,const node &b)
{
node ret;
if(a.all) ret.pre = a.all+b.pre;
else ret.pre = a.pre;
if(b.all) ret.suf = a.suf+b.all;
else ret.suf = b.suf;
ret.mxa = max(max(a.mxa,b.mxa),a.suf+b.pre);
if(!a.all or !b.all) ret.all = 0;
else ret.all = a.all+b.all;
return ret;
}
}tree[N << 1];
void build(int l,int r,int idx)
{
if(l==r) return void(tree[idx] = {a[l],a[l],a[l],a[l]});
int m = (l+r)/2;
build(l,m,idx*2),build(m+1,r,idx*2+1);
tree[idx] = tree[idx*2]+tree[idx*2+1];
}
node read(int l,int r,int idx,int x,int y)
{
if(x>r or y<l) return {0,0,0,0};
if(x<=l and y>=r) return tree[idx];
int m = (l+r)/2;
return read(l,m,idx*2,x,y)+read(m+1,r,idx*2+1,x,y);
}
void print(int l,int r,int idx)
{
cout << l << ' ' << r << endl;
node a = tree[idx];
cout << a.pre << ' ' << a.suf << ' ' << a.mxa << ' ' << a.all << endl;
if(l==r) return;
int m = (l+r)/2;
print(l,m,idx*2),print(m+1,r,idx*2+1);
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R)
{
int Q = L.size();
vector<long long> C(Q);
a = H;
n = a.size();
for(int &x : a) if(x==2) x = 0;
build(0,n-1,1);
for(int j = 0; j < Q; ++j) {
long long l = L[j],r = R[j];
long long ans = LLONG_MAX;
long long tmp = read(0,n-1,1,l,r).mxa;
ans = tmp+(r-l+1-tmp)*2;
/*
ml[l] = H[l]; int nh = H[l];
for(int i = l+1;i <= r;i++)
{
if(H[i]>nh) nh = H[i],ml[i] = (i-l+1)*nh;
else ml[i] = ml[i-1]+;
}
mr[r] = H[r],nh = H[r];
for(int i = r-1;i >= l;i--)
{
if(H[i]>nh) nh = H[i],mr[i] = (r-i+1)*nh;
else mr[i] = mr[i+1]+nh;
}
for(int i = l;i <= r;i++)
{
cout << ml[i] << ' ' << mr[i] << endl;
ans = min(ans,ml[i]+mr[i]-H[i]);
}
*/
C[j] = ans;
}
return C;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
41 ms |
2204 KB |
Output is correct |
3 |
Correct |
130 ms |
9976 KB |
Output is correct |
4 |
Correct |
125 ms |
9972 KB |
Output is correct |
5 |
Correct |
96 ms |
9976 KB |
Output is correct |
6 |
Correct |
139 ms |
9976 KB |
Output is correct |
7 |
Correct |
130 ms |
9976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
41 ms |
2204 KB |
Output is correct |
3 |
Correct |
130 ms |
9976 KB |
Output is correct |
4 |
Correct |
125 ms |
9972 KB |
Output is correct |
5 |
Correct |
96 ms |
9976 KB |
Output is correct |
6 |
Correct |
139 ms |
9976 KB |
Output is correct |
7 |
Correct |
130 ms |
9976 KB |
Output is correct |
8 |
Incorrect |
127 ms |
9976 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |