# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
823344 | Dremix10 | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 1e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;
int A[N],seg[4*N];
void build(int s, int e, int idx){
if(s==e){
seg[idx] = A[s];
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
int query(int s, int e, int idx, int qs, int qe){
if(qs<=s && e<=qe)return seg[idx];
if(s > qe || e < qs)return 0;
int mid = (s+e)/2;
return max(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
}
vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
int n = arr.size();
int q = L.size();
int i,j,k;
vector<ll> ans(q);
// good i is always local minima
//if(i-1 >= x && arr[i-1] < arr[i] || i+1 <= y && arr[i+1] < arr[i])continue;
int cnt = 0;
for(i=0;i<n;i++){
if(arr[i] == 2){
int temp = cnt;
int j = i-1;
while(temp--){
A[j] = cnt;
j--;
}
cnt = 0;
A[i] = 0;
}
else
cnt++;
}
int temp = cnt;
int j = i-1;
while(temp--){
A[j] = cnt;
j--;
}
cnt = 0;
A[i] = 0;
for(i=0;i<n;i++){
cerr<<A[i]<<" ";
}cerr<<endl;
build(0,n-1,1);
for(k=0;k<q;k++){
int x = L[k];
int y = R[k];
ll res = (y-x+1)*2 - query(0,n-1,1,x,y);
ans[k] = res;
}
return ans;
}