이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
struct Node
{
int left_count;
int right_count;
int best_count;
bool pass_through;
};
Node seg_tree[400007];
int N;
vector <int> h;
Node merge(Node l, Node r)
{
Node nw;
nw.pass_through=0;
nw.left_count=l.left_count;
nw.right_count=r.right_count;
nw.best_count=max(l.right_count+r.left_count,max(l.best_count,r.best_count));
if(l.pass_through && r.pass_through)
{
nw.pass_through=1;
}
if(l.pass_through)
{
nw.left_count+=r.left_count;
}
if(r.pass_through)
{
nw.right_count+=l.right_count;
}
return nw;
}
Node build(int l=0, int r=N-1, int node=1)
{
if(l==r)
{
if(h[l]==1)
{
seg_tree[node].left_count=seg_tree[node].right_count=seg_tree[node].best_count=1;
seg_tree[node].pass_through=1;
}
else
{
seg_tree[node].left_count=seg_tree[node].right_count=seg_tree[node].best_count=0;
seg_tree[node].pass_through=0;
}
return seg_tree[node];
}
int m=(l+r)/2;
seg_tree[node]=merge(build(l,m,node*2),build(m+1,r,node*2+1));
return seg_tree[node];
}
Node query(int hl, int hr, int l=0, int r=N-1, int node=1)
{
if(hl<=l && r<=hr)
{
return seg_tree[node];
}
int m=(l+r)/2;
Node nw;
nw.left_count=nw.right_count=nw.best_count=0;
nw.pass_through=1;
if(hl<=m)
{
nw=merge(query(hl,hr,l,m,node*2),nw);
}
if(m+1<=hr)
{
nw=merge(nw,query(hl,hr,m+1,r,node*2+1));
}
return nw;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
N = H.size();
h=H;
build();
vector <ll> ans;
for(int i=0;i<L.size();i++)
{
Node res=query(L[i],R[i]);
ans.pb((R[i]-L[i]+1)*2-res.best_count);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i=0;i<L.size();i++)
| ~^~~~~~~~~
# | 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... |