Submission #377864

#	Time	Username	Problem	Language	Result	Execution time	Memory
377864		cpp219	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	542 ms	262144 KiB

construction

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 5e5 + 9;
const ll inf = 1e9 + 7;
vector<ll> V;
struct city{
    ll x,y,id;
};
city a[N];
struct rect{
    ll x,y,u,v;
};
rect r[N];
ll n,m,Q,x,y,u,v,pre[N],cc,was[N],price,cnt;

bool lf1(city a,city b){
    return a.x < b.x;
}

bool lf2(city a,city b){
    return a.y < b.y;
}

bool cmp1(ll x,ll y){
    return a[x].y < a[y].y;
}

bool cmp2(ll x,ll y){
    return a[x].x < a[y].y;
}

vector<ll> g[N],point[2][N];

struct seg{
    ll l,r,val;
};
vector<seg> pos[2][N];
ll st[4*N],lazy[4*N],total;

ll Find(ll x){
    return lower_bound(V.begin(),V.end(),x) - V.begin() + 1;
}

void compress(){
    sort(V.begin(),V.end()); V.resize(unique(V.begin(),V.end()) - V.begin());
    for (ll i = 1;i <= n;i++){
        a[i].x = Find(a[i].x),a[i].y = Find(a[i].y);
        x = a[i].x; y = a[i].y;
        point[0][x].push_back(i); point[1][y].push_back(i);
    }
    for (ll i = 1;i <= m;i++){
        r[i].x = Find(r[i].x),r[i].y = Find(r[i].y),r[i].u = Find(r[i].u),r[i].v = Find(r[i].v);
        x = r[i].x; y = r[i].y; u = r[i].u; v = r[i].v;

        pos[0][x].push_back({y,v,1}); pos[0][u].push_back({y,v,-1});
        pos[1][y].push_back({x,u,1}); pos[1][v].push_back({x,u,-1});
    }
}
map<LL,ll> mp;

void Pass(ll id){
    ll t = lazy[id]; lazy[id] = 0;
    st[id*2] += t; lazy[id*2] += t;
    st[id*2 + 1] += t; lazy[id*2 + 1] += t;
}

void upd(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        st[id] += val; lazy[id] += val; return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
    st[id] = max(st[id*2],st[id*2 + 1]);
}

ll Get(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return 0;
    if (u <= l&&r <= v) return st[id];
    ll mid = (l + r)/2; Pass(id);
    return max(Get(id*2,l,mid,u,v),Get(id*2 + 1,mid + 1,r,u,v));
}

void process(ll cond){
    memset(st,0,sizeof(st)); memset(lazy,0,sizeof(lazy));
    for (ll i = 1;i < N;i++){
        for (auto j : pos[cond][i]) upd(1,1,N - 1,j.l,j.r,j.val);
        ll sz = point[cond][i].size();
        for (ll j = 1;j < sz;j++){
            ll now = point[cond][i][j],prv = point[cond][i][j - 1];
            ll L = a[prv].x,R = a[now].x;
            if (!cond) L = a[prv].y,R = a[now].y;
            if (Get(1,1,N - 1,L,R)) mp[{now,prv}] = mp[{prv,now}] = 1;
        }
    }
}

struct Edge{
    ll u,v,val;
};
bool fuck(Edge x,Edge y){
    return x.val < y.val;
}
vector<Edge> e,chosen;
void build_graph(ll cond){
    if (!cond) sort(a + 1,a + n + 1,lf1);
    else sort(a + 1,a + n + 1,lf2);
    for (ll i = 1;i < n;i++){
        if (a[i].x == a[i + 1].x||a[i].y == a[i + 1].y){
            ll p = a[i].id,q = a[i + 1].id;
            ll rx = V[a[i].x - 1],ry = V[a[i].y - 1],rx1 = V[a[i + 1].x - 1],ry1 = V[a[i + 1].y - 1];
            if (!mp[{p,q}]) e.push_back({p,q,abs(rx + ry - rx1 - ry1)});//cout<<rx<<" "<<ry<<" x "<<rx1<<" "<<ry1<<"\n";
        }
    }
    //exit(0);
}
ll lab[N];
ll Find_lab(ll u){
    if (lab[u] < 0) return u;
    return lab[u] = Find_lab(lab[u]);
}

void Union(ll r,ll s){
    if (lab[r] > lab[s]) swap(r,s);
    lab[r] += lab[s]; lab[s] = r;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>m>>Q;
    for (ll i = 1;i <= n;i++) cin>>a[i].x>>a[i].y,a[i].id = i,V.push_back(a[i].x),V.push_back(a[i].y);
    for (ll i = 1;i <= m;i++){
        cin>>r[i].x>>r[i].y>>r[i].u>>r[i].v;
        V.push_back(r[i].x); V.push_back(r[i].y); V.push_back(r[i].u); V.push_back(r[i].v);
    }
    compress(); memset(lab,-1,sizeof(lab));
    for (ll i = 1;i < N;i++)
        sort(point[0][i].begin(),point[0][i].end(),cmp1),sort(point[1][i].begin(),point[1][i].end(),cmp2);
    process(0); process(1); build_graph(0); build_graph(1); sort(e.begin(),e.end(),fuck);
    //for (auto i : e) cout<<i.u<<" "<<i.v<<" "<<i.val<<"\n";
    for (auto i : e){
        ll r = Find_lab(i.u),s = Find_lab(i.v);
        if (r != s) Union(r,s),total += i.val,chosen.push_back(i);
    }
    reverse(chosen.begin(),chosen.end());
    pre[0] = chosen[0].val;
    for (ll i = 1;i < chosen.size();i++) pre[i] = pre[i - 1] + chosen[i].val;
    for (ll i = 1;i <= n;i++){
        ll now = Find_lab(i);
        if (!was[now]) cc++; was[now] = 1;
    }
    while(Q--){
        ll inc = 0;
        cin>>price>>cnt; cnt -= cc;
        if (cnt < 0){
            cout<<"-1\n"; continue;
        }
        ll l,mid,h; l = 0; h = chosen.size() - 1;
        while(l <= h){
            mid = (l + h)/2;
            if (chosen[mid].val < price) h = mid - 1;
            else l = mid + 1;
        }
        //cout<<h; return 0;
        ll p = min(cnt - 1,h);
        if (p >= 0) inc = pre[p] - (p + 1)*price;
        cout<<total - inc + cc*price<<"\n";
    }
}

Compilation message (stderr)

construction.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
construction.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
construction.cpp: In function 'int main()':
construction.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (ll i = 1;i < chosen.size();i++) pre[i] = pre[i - 1] + chosen[i].val;
      |                   ~~^~~~~~~~~~~~~~~
construction.cpp:165:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  165 |         if (!was[now]) cc++; was[now] = 1;
      |         ^~
construction.cpp:165:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  165 |         if (!was[now]) cc++; was[now] = 1;
      |                              ^~~
construction.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  142 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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