| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 133767 | dorijanlendvaj | 모임들 (IOI18_meetings) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}