| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 133767 | dorijanlendvaj | Meetings (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 x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N=750010,M=1<<20,MOD=1000000007;
const char en='\n';
const ll LLINF=1ll<<60;
struct no
{
int lon=0,pref=0,suf=0;
int sz=1;
};
no merge(no a,no b)
{
no x;
x.sz=a.sz+b.sz;
x.lon=max(a.lon,b.lon);
x.lon=max(x.lon,a.suf+b.pref);
if (a.pref==a.sz) x.pref=a.pref+b.pref;
else x.pref=a.pref;
if (b.suf==b.sz) x.suf=a.suf+b.suf;
else x.suf=b.suf;
return x;
}
no seg[M+N];
no get(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[i];
if (lo>=r || hi<=l) return seg[0];
int mid=(lo+hi)/2;
return merge(get(l,r,lo,mid,i*2),get(l,r,mid,hi,i*2+1));
}
vl minimum_costs(vi H, vi L, vi R) {
vi h=H,l=L,r=R;
int n=h.size(),q=l.size();
for (int i=0;i<n;++i) seg[i+M].lon=seg[i+M].pref=seg[i+M].suf=h[i]==1;
//cout<<"in1 done"<<endl;
for (int i=M-1;i>0;--i) if (i*2+1<M+N) seg[i]=merge(seg[i*2],seg[i*2+1]);
vl ans;
for (int i=0;i<q;++i) ans.pb((r[i]-l[i]+1)*2-get(l[i],r[i]+1).lon);
return ans;
}