| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283737 |
2020-08-26T06:33:12 Z |
최은수(#5746) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
32 ms |
3840 KB |
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct dsu
{
int pa[mx];
int par(int x)
{
if(pa[x]==0)
return x;
return pa[x]=par(pa[x]);
}
inline void uni(int x,int y)
{
x=par(x);
y=par(y);
if(x==y)
return;
pa[x]=y;
return;
}
}uf;
struct seg
{
int t[2400010];
bool t2[2400010];
void init(int n,int s,int e)
{
t[n]=0;
t2[n]=0;
if(s==e)
return;
int m=s+(e-s)/2;
init(n*2,s,m);
init(n*2+1,m+1,e);
return;
}
void upd(int n,int s,int e,int S,int E,int p)
{
if(s>E||S>e)
return;
if(S<=s&&e<=E)
{
t[n]+=p;
t2[n]=t[n]>0?1:(s==e?0:t[n*2]||t[n*2+1]);
return;
}
int m=s+(e-s)/2;
upd(n*2,s,m,S,E,p);
upd(n*2+1,m+1,e,S,E,p);
t2[n]=t[n]>0?1:t2[n*2]||t2[n*2+1];
return;
}
bool query(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return 0;
if(t[n]>0)
return 1;
if(S<=s&&e<=E)
return t2[n];
int m=s+(e-s)/2;
return query(n*2,s,m,S,E)||query(n*2+1,m+1,e,S,E);
}
}st;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,c;
cin>>n>>m>>c;
vector<pi>v(n);
vector<pair<pi,pi> >mv(m);
vector<int>cxv,cyv;
for(pi&t:v)
cin>>t.fi>>t.se,cxv.eb(t.fi),cyv.eb(t.se);
for(auto&t:mv)
cin>>t.fi.fi>>t.se.fi>>t.fi.se>>t.se.se,
cxv.eb(t.fi.fi),cxv.eb(t.fi.se),cyv.eb(t.se.fi),cyv.eb(t.se.se);
sort(all(cxv));
sort(all(cyv));
cxv.erase(unique(all(cxv)),cxv.end());
cyv.erase(unique(all(cyv)),cyv.end());
for(pi&t:v)
t.fi=upper_bound(all(cxv),t.fi)-cxv.begin(),
t.se=upper_bound(all(cyv),t.se)-cyv.begin();
v.insert(v.begin(),v[0]);
for(auto&t:mv)
t.fi.fi=upper_bound(all(cxv),t.fi.fi)-cxv.begin(),
t.fi.se=upper_bound(all(cxv),t.fi.se)-cxv.begin(),
t.se.fi=upper_bound(all(cyv),t.se.fi)-cyv.begin(),
t.se.se=upper_bound(all(cyv),t.se.se)-cyv.begin();
int xn=cxv.size(),yn=cyv.size();
vector<int>sv;
for(int i=0;i++<n;)
sv.eb(i);
vector<vector<pi> >xsv(xn+1);
vector<vector<pi> >ysv(yn+1);
sort(all(sv),[&](const int&x,const int&y){return v[x]<v[y];});
for(int i=1;i<n;i++)
if(v[sv[i]].fi==v[sv[i-1]].fi)
xsv[v[sv[i]].fi].eb(sv[i-1],sv[i]);
sort(all(sv),[&](const int&x,const int&y){return pi(v[x].se,v[x].fi)<pi(v[y].se,v[y].fi);});
for(int i=1;i<n;i++)
if(v[sv[i]].se==v[sv[i-1]].se)
ysv[v[sv[i]].se].eb(sv[i-1],sv[i]);
vector<vector<pi> >xqv(xn+1),xdv(xn+1);
vector<vector<pi> >yqv(yn+1),ydv(yn+1);
for(auto&t:mv)
xqv[t.fi.fi].eb(t.se),xdv[t.fi.se].eb(t.se),
yqv[t.se.fi].eb(t.fi),ydv[t.se.se].eb(t.fi);
vector<pair<int,pi> >ev;
st.init(1,1,yn);
for(int i=0;i++<xn;)
{
for(pi&t:xqv[i])
st.upd(1,1,yn,t.fi,t.se,1);
for(pi&t:xsv[i])
if(!st.query(1,1,yn,v[t.fi].se,v[t.se].se))
ev.eb(cyv[v[t.se].se-1]-cyv[v[t.fi].se-1],t);
for(pi&t:xdv[i])
st.upd(1,1,yn,t.fi,t.se,-1);
}
st.init(1,1,xn);
for(int i=0;i++<yn;)
{
for(pi&t:yqv[i])
st.upd(1,1,xn,t.fi,t.se,1);
for(pi&t:ysv[i])
if(!st.query(1,1,xn,v[t.fi].fi,v[t.se].fi))
ev.eb(cxv[v[t.se].fi-1]-cxv[v[t.fi].fi-1],t);
for(pi&t:ydv[i])
st.upd(1,1,xn,t.fi,t.se,-1);
}
vector<int>wv;
sort(all(ev));
for(auto&t:ev)
{
if(uf.par(t.se.fi)!=uf.par(t.se.se))
wv.eb(t.fi);
uf.uni(t.se.fi,t.se.se);
}
vector<ll>ps(1,0);
for(int&t:wv)
ps.eb(ps.back()+t);
for(int i=0;i<c;i++)
{
int b,h;
cin>>b>>h;
if((int)wv.size()+h<n)
{
cout<<-1<<'\n';
continue;
}
int pos=max(n-h,(int)(lower_bound(all(wv),b)-wv.begin()));
cout<<(ps[pos]+(ll)(n-pos)*b)<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
