이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define red 1
#define blue 0
const int N = 200010;
long long seg[4 * N] , lazy[4 * N] , dp[N];
vector< pair<int,bool> > v;
int n , nxt[N];
long long getmin(int s,int e,int idx,int l,int r){
if(s > r || e < l) return 1e18;
if(s >= l && e <= r) return seg[idx] + lazy[idx];
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
seg[idx] += lazy[idx];
lazy[idx] = 0;
return min(getmin(s,(s+e)/2,idx*2,l,r),getmin((s+e)/2+1,e,idx*2+1,l,r));
}
long long update(int s,int e,int idx,int l,int r,long long val){
if(s > r || e < l) return seg[idx] + lazy[idx];
if(s >= l && e <= r){
lazy[idx] += val;
return seg[idx] + lazy[idx];
}
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
lazy[idx] =0 ;
return seg[idx] = min(update(s,(s+e)/2,idx*2,l,r,val),update((s+e)/2+1,e,idx*2+1,l,r,val));
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int j =0 ;
for(int i=0;i<r.size();i++){
while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
v.push_back(make_pair(r[i],red));
}
while(j < b.size()) v.push_back(make_pair(b[j++],blue));
n = v.size();
nxt[n] = n;
for(int i=n-1;i>=0;i--){
if(v[i].second != v[i+1].second) nxt[i] = i + 1; else nxt[i] = nxt[i+1];
}
for(int i=n-1;i>=0;i--){
if(nxt[i] == n){
dp[i] = 1e18;
update(0,n,1,i,i,dp[i]);
continue;
}
dp[i] = 1e18;
if(nxt[i] == i + 1){
long long sum = 0 ;
for(int j=i+1;j<nxt[i+1];j++){
update(0,n,1,j,j,sum);
sum += v[j].first - v[i].first;
}
for(int j=nxt[i+1];j<=nxt[nxt[i+1]];j++){
update(0,n,1,j,j,-getmin(0,n,1,j,j));
update(0,n,1,j,j,dp[j] + sum);
if(j < nxt[nxt[i+1]]) sum += v[j].first - v[i+1].first;
}
dp[i] = min(dp[i],getmin(0,n,1,i+2,nxt[nxt[i+1]]));
update(0,n-1,1,i,i,dp[i]);
}
else{
int cur = nxt[i] ;
int cur2 = nxt[cur] - 1;
int num = cur - i;
long long s = 0 ;
if(cur2 - cur < num){
if(cur+1 <= cur2) update(0,n,1,cur+1,cur2,v[cur].first - v[i].first);
}
else{
update(0,n,1,cur+1,cur+num-1,v[cur].first-v[i].first);
if(cur+num <= cur2){
update(0,n,1,cur+num,cur2,v[cur-1].first - v[i].first);
}
}
cur2++;
if(cur2 - cur < num) s = v[cur].first - v[i].first;
else s = v[cur-1].first - v[i].first;
update(0,n,1,cur2,nxt[cur2],s);
dp[i] = getmin(0,n,1,cur+1,nxt[cur2]);
update(0,n,1,i,i,dp[i]);
}
}
return dp[0];
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<r.size();i++){
^
wiring.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
^
wiring.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < b.size()) v.push_back(make_pair(b[j++],blue));
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |