| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 836723 | IS_Rushdi | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct item{
int l,r,m;
};
struct segment_tree{
vector<vector<item>>st;
vector<vector<pair<int,int>>>range;
segment_tree(int n,vector<int>a){
int q = 0;
for(int i = 1; ; i+=i){
if(i >= n){
st.assign(log2(i)+1,vector<item>());
range.assign(log2(i)+1,vector<pair<int,int>>());
int q = i;
for(int j = 0; j < st.size(); j++){
st[j].assign(q,{0,0,0});
range[j].assign(q,{0,0});
q/=2;
}
break;
}
}
for(int i = 0; i < st[0].size(); i++){
range[0][i].first = i;
range[0][i].second = i;
}
for(int 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(int i = 1; i < st.size(); i++){
for(int 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;
int x = range[i-1][j*2].second-range[i-1][j*2].first+1;
int 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;
}
}
}
int findl(int left,int right,int i,int j){
if(i < 0) return 0;
int l = range[i][j].first;
int r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].l;
else findl(left,right,i-1,j*2);
}
int findr(int left,int right,int i,int j){
if(i < 0) return 0;
int l = range[i][j].first;
int r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].r;
else findr(left,right,i-1,j*2+1);
}
int find(int left,int right,int i=-2,int j=-2){
if(i == -2){
i = st.size()-1;
j = 0;
}
if(i == -1) return 0;
int l = range[i][j].first;
int r = range[i][j].second;
int 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<int> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int q = L.size();
int n = H.size();
vector<int> ans(q);
segment_tree st(n,H);
for(int v = 0; v < q; v++){
int l = L[v];
int r = R[v];
ans[v] = (2*(r-l+1))-st.find(l,r);
}
return ans;
}
// int main(){
// int n,m; cin >> n >> m;
// vector<int>a(n);
// vector<int>b(m),c(m);
// for(int i = 0; i < n; i++) cin >> a[i];
// for(int i = 0; i < m; i++) cin >> b[i] >> c[i];
// vector<int>ans = minimum_costs(a,b,c);
// for(int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
// }