Submission #43285

#	Time	Username	Problem	Language	Result	Execution time	Memory
43285		smu201111192	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	2325 ms	168572 KiB

construction

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 2000001;
int n,m,q,xx[MAXN],yy[MAXN];
struct rect{
    int y1,x1,y2,x2;
    void read(){ cin>>y1>>x2>>y2>>x2; }
    void rotate(){ swap(x1,y1); swap(x2,y2); }
}r[MAXN];
vector<pair<int,int> > event;
struct segTree{
    vector<int> lazy,tree,comp;
    int lb(int x){ return lower_bound(comp.begin(),comp.end(),x) - comp.begin() + 1; }
    void in(int x){ comp.push_back(x);}
    void clear(){ lazy.clear(); tree.clear(); comp.clear();}
    void set(){
        sort(comp.begin(),comp.end());
        comp.erase(unique(comp.begin(),comp.end()),comp.end());
        tree.resize(comp.size() * 4 + 4, 0);
        lazy.resize(comp.size() * 4 + 4, -1);
    }
    void push(int node,int st,int ed){
        if(lazy[node] == -1)return;
        tree[node] = lazy[node];
        if(st != ed){
            lazy[2 * node] = lazy[node];
            lazy[2 * node + 1] = lazy[node];
        }
        lazy[node] = -1;
    }
    void update(int node,int st,int ed,int l,int r,int val){
        push(node,st,ed);
        if(st > r || ed < l)return;
        if(st >= l && ed <= r){
            lazy[node] = val;
            push(node,st,ed);
            return;
        }
        update(node*2,st,(st+ed)/2,l,r,val);
        update(node*2+1,(st+ed)/2+1,ed,l,r,val);
        tree[node] = max(tree[node*2],tree[node*2+1]);
    }
    int query(int node,int st,int ed,int l,int r){
        push(node,st,ed);
        if(st > r || ed < l) return -1e9;
        if(st >= l && ed <= r)return tree[node];
        auto L = query(node*2,st,(st+ed)/2,l,r);
        auto R = query(node*2+1,(st+ed)/2+1,ed,l,r);
        return max(L,R);
    }
    int query(int l,int r){
        l = lb(l); r = lb(r);
        return query(1,1,comp.size(),l,r);
    }
    void update(int l,int r,int val){
        l = lb(l); r = lb(r);
        update(1,1,comp.size(),l,r,val);
    }
}ft;
vector<pair<int,int> > vc[MAXN];
struct info{
    int x,type,idx;
    bool operator < (const info in)const{
        if(x != in.x)return x < in.x;
        if(type != in.type) return type < in.type;
        return idx < in.idx;
    }
};
struct edge{
    int u,v,w;
    bool operator < (const edge e)const{
        return w < e.w;
    }
};
vector<edge> e;
void solve(){
    vector<info> event;
    ft.clear();
    for(int i = 0; i < MAXN; i++) vc[i].clear();
    for(int i = 1; i <= n; i++) ft.in(yy[i]);
    for(int i = 1; i <= m; i++) { ft.in(r[i].y1);  ft.in(r[i].y2); }
    ft.set();
    for(int i = 1; i <= n; i++){
        event.push_back({xx[i],1,i});
    }
    for(int i = 1; i <= m; i++){
        event.push_back({r[i].x1,0,i});
        event.push_back({r[i].x2,2,i});
    }
    sort(event.begin(),event.end());
    for(int i = 0; i < event.size(); i++){
        int type = event[i].type;
        int idx = event[i].idx;
        if(type == 0){  //line open
            ft.update(r[idx].y1,r[idx].y2,r[idx].x1);
        }
        else if(type == 1){ //dot
            int loc = ft.lb(yy[idx]);
            if(vc[loc].size()){
                int last = vc[loc].back().second;
                if(ft.query(yy[last],yy[last]) < xx[last]){
                    e.push_back({last,idx,abs(xx[idx]-xx[last])});
                }
            }
            vc[loc].push_back(make_pair(xx[idx],idx));
        }
        else{  //line close
            ft.update(r[idx].y1,r[idx].y2,r[idx].x2);
        }
    }
    for(int i = 1; i <= n; i++) swap(xx[i],yy[i]);
    for(int i = 1; i <= m; i++) r[i].rotate();
}
int parent[MAXN];
int find(int u){
    return u == parent[u] ? u : parent[u] = find(parent[u]);
}
void mrg(int u,int v){
    u = find(u);
    v = find(v);
    if(u == v)return;
    parent[u] = v;
}
long long cost[MAXN];
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        cin >> yy[i] >> xx[i];
    for(int i = 1; i <= m; i++) r[i].read();
    solve();
    solve();
    for(int i = 0; i < MAXN; i++) parent[i] = i;
    sort(e.begin(),e.end());
    for(int i = 1; i < MAXN; i++)cost[i] = 3e18;
    int piv = 0;
    vector<pair<int,int> > use;
    use.push_back(make_pair(0,0));
    for(auto x:e){
        int u = x.u; int v = x.v; int w = x.w;
        if(find(u) == find(v)) continue;
        ++piv; cost[piv] = cost[piv-1] + w;
        use.push_back(make_pair(piv,w));
    }
    for(int i = 1; i <= q; i++){
        long long b,h;
        cin >> b >> h;
        if(h >= n) h = n;
        //컴포넌트를 n 개로 만들려면 엣지를 하나도 연결 안하면됨
        if(cost[n-h] == 3e18) { cout<<-1<<"\n"; continue; }
        long long lo = n - h; long long hi = min(h,(long long)use.size()-1);
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(use[mid].second <= b){
                lo = mid + 1;
            }
            else hi = mid - 1;
        }
        int euse = lo - 1;
        long long ans = cost[euse] + 1LL * (n-euse) * b;
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void solve()':
construction.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < event.size(); i++){
                      ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30