| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 836655 | 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<int>>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<int>());
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);
range[j].assign(q,{0,0});
q/=2;
}
q = i;
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] = a[i];
}
for(int i = 1; i < st.size(); i++){
for(int j = 0; j < st[i].size(); j++){
int node1 = st[i-1][j*2];
int node2 = st[i-1][j*2+1];
st[i][j] = node1+node2;
range[i][j].first = range[i-1][j*2].first;
range[i][j].second = range[i-1][j*2+1].second;
}
}
}
int findL(int i,int j,int left,int right){
if(i < 0) return 0;
int l = range[i][j].first;
int r = range[i][j].second;
int x = r-l+1;
if(l >= left && r <= right && x == st[i][j]) return x;
else return findL(i-1,j*2,left,right);
}
int findR(int i,int j,int left,int right){
if(i < 0) return 0;
int l = range[i][j].first;
int r = range[i][j].second;
int x = r-l+1;
if(l >= left && r <= right && st[i][j] == x) return st[i][j];
else return findR(i-1,j*2+1,left,right);
}
int find(int left,int right,int i=-1,int j=-1){
if(i == -1){
i = st.size()-1;
j = 0;
}
int l = range[i][j].first;
int r = range[i][j].second;
if(l > right || r < left) return 0;
else{
int ans = 0;
if(l >= left && r <= right){
ans = max(findR(i,j,left,right),findL(i,j,left,right));
}else{
ans = max(find(left,right,i-1,j*2+1),find(left,right,i-1,j*2));
}
ans = max(ans,findR(i-1,j*2,left,right)+findL(i-1,j*2+1,left,right));
return ans;
}
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int q = L.size();
int n = H.size();
vector<long long> 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<long long>ans = minimum_costs(a,b,c);
for(int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}