Submission #377924

#TimeUsernameProblemLanguageResultExecution timeMemory
377924cpp219도로 건설 사업 (JOI13_construction)C++14
0 / 100
205 ms231148 KiB
#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 || (a.x == b.x&&a.y < b.y); } bool lf2(city a,city b){ return a.y < b.y || (a.y == b.y&&a.x < b.x); } 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].x; } 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 + 1].push_back({y,v,-1}); pos[1][y].push_back({x,u,1}); pos[1][v + 1].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++){ //cout<<pos[cond][i].size(); exit(0); for (auto j : pos[cond][i]) upd(1,1,N - 1,j.l + 1,j.r - 1,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; //cout<<prv<<" "<<now<<" "<<Get(1,1,N - 1,L,R)<<"\n"; if (Get(1,1,N - 1,L + 1,R - 1)) mp[{now,prv}] = mp[{prv,now}] = 1; } //exit(0); } } 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 ((!cond&&a[i].x == a[i + 1].x)||(cond&&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); //return 0; 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"; return 0; 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()); if (chosen.size()){ 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:164:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (ll i = 1;i < chosen.size();i++) pre[i] = pre[i - 1] + chosen[i].val;
      |                       ~~^~~~~~~~~~~~~~~
construction.cpp:168:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  168 |         if (!was[now]) cc++; was[now] = 1;
      |         ^~
construction.cpp:168:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  168 |         if (!was[now]) cc++; was[now] = 1;
      |                              ^~~
construction.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...