| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 836701 | IS_Rushdi | Meetings (IOI18_meetings) | C++17 | 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>
using namespace std;
struct item{
long long l,r,m;
};
struct segment_tree{
vector<vector<item>>st;
vector<vector<pair<long long,long long>>>range;
segment_tree(long long n,vector<int>a){
long long q = 0;
for(long long i = 1; ; i+=i){
if(i >= n){
st.assign(log2(i)+1,vector<item>());
range.assign(log2(i)+1,vector<pair<long long,long long>>());
long long q = i;
for(long long j = 0; j < st.size(); j++){
st[j].assign(q,{0,0,0});
range[j].assign(q,{0,0});
q/=2;
}
q = i;
break;
}
}
for(long long i = 0; i < st[0].size(); i++){
range[0][i].first = i;
range[0][i].second = i;
}
for(long long i = 0; i < n; i++){
st[0][i].l = (a[i]==1);
st[0][i].r = (a[i]==1);
st[0][i].m = (a[i]==1);
}
for(long long i = 1; i < st.size(); i++){
for(long long j = 0; j < st[i].size(); j++){
item node1 = st[i-1][j*2];
item node2 = st[i-1][j*2+1];
st[i][j].l = node1.l;
st[i][j].r = node2.r;
long long x = range[i-1][j*2].second-range[i-1][j*2].first+1;
long long x2 = range[i-1][j*2+1].second-range[i-1][j*2+1].first+1;
if(node1.l == x){
st[i][j].l = node1.l + node2.l;
}
if(node2.r == x2){
st[i][j].r = node1.r + node2.r;
}
st[i][j].m = max(node1.m,node2.m);
st[i][j].m = max(st[i][j].m,node1.r+node2.l);
st[i][j].m = max(st[i][j].m,st[i][j].l);
st[i][j].m = max(st[i][j].m,st[i][j].r);
range[i][j].first = range[i-1][j*2].first;
range[i][j].second = range[i-1][j*2+1].second;
}
}
}
long long findl(long long left,long long right,long long i,long long j){
if(i < 0) return 0;
long long l = range[i][j].first;
long long r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].l;
else findl(left,right,i-1,j*2);
}
long long findr(long long left,long long right,long long i,long long j){
if(i < 0) return 0;
long long l = range[i][j].first;
long long r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].r;
else findr(left,right,i-1,j*2+1);
}
long long find(long long left,long long right,long long i=-1,long long j=-1){
if(i == -1){
i = st.size()-1;
j = 0;
}
long long l = range[i][j].first;
long long r = range[i][j].second;
long long ans = findl(left,right,i-1,j*2+1)+findr(left,right,i-1,j*2);
if(l > right || r < left) return ans;
else if(l >= left && r <= right){
ans = max(ans,st[i][j].m);
return ans;
}
else{
ans = max(ans,max(find(left,right,i-1,j*2+1),find(left,right,i-1,j*2)));
return ans;
}
}
};
vector<long long>task(vector<int> H, vector<int> L,vector<int> R){
long long q = L.size();
long long n = H.size();
vector<long long > ans(q);
vector<vector<long long >> mn(n,vector<long long>(n,1e18));
for(long long i = 0; i < n; i++){
mn[i][i] = H[i];
long long curr = H[i];
for(long long j = i-1; j >= 0; j--){
curr = max(curr,H[j]*1ll);
mn[j][i] = curr;
}curr = H[i];
for(long long j = i+1; j < n; j++){
curr = max(curr,H[j]*1ll);
mn[j][i] = curr;
}
}
for(long long i = 0; i < n; i++){
for(long long j = 1; j < n; j++){
mn[j][i] += mn[j-1][i];
}
}
for(long long v = 0; v < q; v++){
long long l = L[v];
long long r = R[v];
long long cnt = 1e18;
for(long long i = l; i <= r; i++){
if(l == 0)cnt = min(cnt,mn[r][i]);
else cnt = min(cnt,mn[r][i]-mn[l-1][i]);
}
ans[v] = cnt;
}
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
long long q = L.size();
long long n = H.size();
if(n <= 5000 && q <= 5000) return task(H,L,R);
vector<long long> ans(q);
segment_tree st(n,H);
for(long long v = 0; v < q; v++){
long long l = L[v];
long long r = R[v];
ans[v] = (2*(r-l+1))-st.find(l,r);
}
return ans;
}
int main(){
long long n,m; cin >> n >> m;
vector<int>a(n);
vector<int>b(m),c(m);
for(long long i = 0; i < n; i++) cin >> a[i];
for(long long i = 0; i < m; i++) cin >> b[i] >> c[i];
vector<long long>ans = minimum_costs(a,b,c);
for(long long i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}