| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 992576 | PoPularPlusPlus | Road Construction (JOI21_road_construction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second
struct item {
ll pp, pn,np,nn;
};
struct Seg {
int siz;
vector<item> v;
item nutral = {(ll)1e18, (ll)1e18, (ll)1e18, (ll)1e18};
item single(ll a , ll b){
return {a + b , a - b , -a + b, - a - b};
}
item merge(item a , item b){
return {min(a.pp,b.pp), min(a.pn,b.pn) , min(a.np,b.np), min(a.nn,b.nn)};
}
void init(int n){
siz=1;
while(siz < n)siz*=2;
v.assign(siz * 2 , nutral);
}
void build(vector<ll>& a , vector<ll>& b , int x , int lx , int rx){
if(rx -lx == 1){
if(lx < a.size()){
v[x] = single(a[lx], b[lx]);
}
return;
}
int m = (lx + rx)/2;
build(a , b , 2 * x + 1 , lx , m);
build(a , b , 2 * x + 2 , m , rx);
v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
}
void build(vector<ll>& a , vector<ll>& b){
build(a,b,0,0,siz);
}
void set(int i , item val , int x , int lx , int rx){
if(rx - lx == 1){
v[x] = val;
return;
}
int m = (lx + rx)/2;
if(i < m)set(i , val , 2 * x + 1 , lx , m);
else set(i , val, 2 * x + 2 , m , rx);
v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
}
void set(int i , item val){
set(i , val ,0 , 0 , siz);
}
item range(int l , int r , int x , int lx , int rx){
if(l >= rx || lx >= r)return nutral;
if(lx >= l && rx <= r)return v[x];
int m = (lx + rx)/2;
return merge(range(l , r , 2 * x + 1 , lx , m) , range(l , r , 2 * x + 2 , m ,rx));
}
item range(int l ,int r){
return range(l , r , 0 , 0 , siz);
}
};
void solve(){
int n , k;
cin >> n >> k;
vector<ll> a(n) , b(n);
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
vector<pair<ll,ll>> v;
for(int i = 0; i < n; i++){
v.pb(mp(b[i] , a[i]));
}
sort(all(v));
for(int i = 0; i < n; i++){
a[i] = v[i].vs;
b[i] = v[i].vf;
}
Seg st,st1;
st.init(n + 5);
st.build(a , b);
st1.init(n + 5);
vector<pair<int,int>> xsort;
for(int i = 0; i < n; i++){
xsort.pb(mp(v[i].vs , i));
}
sort(all(xsort));
set<
for(int i = 0; i < n; i++){
st.set(xsort[i].vs , nutral);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}