| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1221010 | cpdreamer | 모임들 (IOI18_meetings) | C++20 | 0 ms | 0 KiB |
#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
int t[(int)1e5+1][18], a[(int)1e5+1];
void build(int n) {
for(int i = 1; i <= n; ++i) t[i][0] = a[i];
for(int k = 1; k < 18; ++k) {
for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
t[i][k] = max(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
}
}
}
int query(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return max(t[l][k], t[r - (1 << k) + 1][k]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int q=(ll)L.size();
int n=(ll)H.size();
V<int>v1;
V<P<int,int>>v2;
for (int i=0;i<n;i++) {
if (H[i]==2) {
v1.pb(i);
}
}
for (int i=1;i<(int)v1.size();i++) {
v2.pb({v1[i-1],v1[i]});
}
for (int i=0;i<(int)v2.size();i++) {
a[i+1]=v2[i].S-v2[i].F-1;
}
V<ll>C;
build((int)v2.size());
for (int i=0;i<q;i++) {
int l=L[i],r=R[i];
int ans1=-1;
int ans2=-1;
int lb=0,rb=(int)v1.size()-1;
while (lb<=rb) {
int m=lb+(rb-lb)/2;
if (v1[m]>=l) {
ans1=m;
rb=m-1;
}
else
lb=m+1;
}
lb=0,rb=(int)v1.size()-1;
while (lb<=rb) {
int m=lb+(rb-lb)/2;
if (v1[m]<=r) {
ans2=m;
lb=m+1;
}
else
rb=m-1;
}
if (ans2==-1 ) {
C.pb(r-l+1);
continue;
}
if (v1[ans2]<l) {
C.pb(r-l+1);
continue;
}
int x=r-l+1+min(r-v1[ans1]+1,v1[ans2]-l+1);
lb=ans1+1,rb=ans2;
if (lb>rb) {
C.pb(x);
continue;
}
x=min(x,2*(r-l+1)-query(lb,rb));
C.pb(x);
}
return C;
}