oj.uz

Submission #43290

# Submission time Handle Problem Language Result Execution time Memory
43290 2018-03-13T07:37:36 Z smu201111192 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 2715 ms 262144 KB 
#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>>x1>>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, -1);
        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{
            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 tot;
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;
    tot = n;
    use.push_back(make_pair(0,0));
    vector<pair<int,int> > vc;
    for(auto x:e){
        int u = x.u; int v = x.v; int w = x.w;
        vc.push_back(make_pair(min(u,v),max(u,v)));
        if(find(u) == find(v)) continue;
        mrg(u,v);
        tot--;
        ++piv; cost[piv] = cost[piv-1] + w;
        use.push_back(make_pair(piv,w));
    }
    //sort(vc.begin(),vc.end());
    //for(auto x:vc)cout<<x.first<<' '<<x.second<<endl;
    for(int i = 1; i <= q; i++){
        long long b,h;
        cin >> b >> h;
        //컴포넌트를 n 개로 만들려면 엣지를 하나도 연결 안하면됨
        if(h < tot) { cout<<-1<<"\n"; continue; }
        long long lo = n - h; long long hi = use.size() - 1; //euse
        lo = max(lo,0LL);
        int euse = lo;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(use[mid].second < b){
                lo = mid + 1;
                euse = mid;
            }
            else hi = mid - 1;
        }
        long long ans = cost[euse] + 1LL * (n-euse) * b;
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 71760 KB Output is correct
2 Correct 586 ms 86948 KB Output is correct
3 Correct 563 ms 90508 KB Output is correct
4 Correct 520 ms 95716 KB Output is correct
5 Correct 558 ms 100952 KB Output is correct
6 Correct 563 ms 100952 KB Output is correct
7 Correct 360 ms 106880 KB Output is correct
8 Correct 344 ms 117720 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2382 ms 137724 KB Output is correct
2 Correct 2280 ms 137936 KB Output is correct
3 Correct 2441 ms 137960 KB Output is correct
4 Correct 2390 ms 137960 KB Output is correct
5 Correct 1288 ms 137960 KB Output is correct
6 Correct 569 ms 137960 KB Output is correct
7 Correct 2393 ms 149424 KB Output is correct
8 Correct 701 ms 149424 KB Output is correct
9 Correct 713 ms 151900 KB Output is correct
10 Correct 1006 ms 183660 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 183660 KB Output is correct
2 Correct 832 ms 183660 KB Output is correct
3 Correct 829 ms 183660 KB Output is correct
4 Correct 751 ms 183660 KB Output is correct
5 Correct 697 ms 183660 KB Output is correct
6 Correct 819 ms 199836 KB Output is correct
7 Correct 925 ms 206352 KB Output is correct
8 Correct 830 ms 217052 KB Output is correct
9 Correct 558 ms 228796 KB Output is correct
10 Correct 597 ms 245368 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2681 ms 262144 KB Output is correct
2 Correct 1614 ms 262144 KB Output is correct
3 Correct 2603 ms 262144 KB Output is correct
4 Correct 775 ms 262144 KB Output is correct
5 Correct 2646 ms 262144 KB Output is correct
6 Correct 799 ms 262144 KB Output is correct
7 Correct 2471 ms 262144 KB Output is correct
8 Correct 2715 ms 262144 KB Output is correct
9 Correct 906 ms 262144 KB Output is correct
10 Correct 1215 ms 262144 KB Output is correct
11 Correct 643 ms 262144 KB Output is correct