| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 289821 |
2020-09-03T06:09:00 Z |
최은수(#5769) |
None (JOI12_invitation) |
C++17 |
|
1281 ms |
80316 KB |
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#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=100010;
struct group
{
int p,q,r,s,t;
group(){}
group(int p,int q,int r,int s,int t):p(p),q(q),r(r),s(s),t(t){}
};
struct event
{
int h;
int l,r;
int cd;
event(){}
event(int h,int l,int r,int cd):h(h),l(l),r(r),cd(cd){}
bool operator<(const event&x)const
{
return h==x.h?(cd==x.cd?l>x.l:cd>x.cd):h<x.h;
}
};
vector<group>v;
bool chk[mx];
struct seg
{
vector<int>t[mx*8];
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].eb(p);
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);
return;
}
void query(int n,int s,int e,int x,vector<int>&v)
{
for(int&e:t[n])
v.eb(e);
t[n].clear();
if(s==e)
return;
int m=s+(e-s)/2;
if(x>m)
query(n*2+1,m+1,e,x,v);
else
query(n*2,s,m,x,v);
return;
}
}stdog,stcat;
struct seg2
{
int t[mx*8];
void init(int n,int s,int e)
{
if(s==e)
{
t[n]=s;
return;
}
int m=s+(e-s)/2;
init(n*2,s,m);
init(n*2+1,m+1,e);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
void del(int n,int s,int e,int x)
{
if(s==e)
{
t[n]=inf;
return;
}
int m=s+(e-s)/2;
if(x>m)
del(n*2+1,m+1,e,x);
else
del(n*2,s,m,x);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
int query(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return inf;
if(S<=s&&e<=E)
return t[n];
int m=s+(e-s)/2;
return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
}
}stmd,stmc;
bool visd[mx*2],visc[mx*2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,c;
cin>>a>>b>>c;
int n;
cin>>n;
v.resize(n);
for(auto&t:v)
cin>>t.p>>t.q>>t.r>>t.s>>t.t;
vector<int>cv1,cv2;
for(auto&t:v)
cv1.eb(t.p),cv1.eb(t.q+1),
cv2.eb(t.r),cv2.eb(t.s+1);
cv1.eb(c),cv1.eb(c+1);
sort(all(cv1));
cv1.erase(unique(all(cv1)),cv1.end());
sort(all(cv2));
cv2.erase(unique(all(cv2)),cv2.end());
{
if(cv1[0]!=1||cv2[0]!=1||cv1.back()!=a+1||cv2.back()!=b+1)
return cout<<-1<<endl,0;
vector<pi>v1,v2;
for(auto&t:v)
v1.eb(t.p,t.q),v2.eb(t.r,t.s);
sort(all(v1)),sort(all(v2));
int mx=0;
for(pi&t:v1)
{
if(t.fi>mx+1)
return cout<<-1<<endl,0;
mx=max(mx,t.se);
}
mx=0;
for(pi&t:v2)
{
if(t.fi>mx+1)
return cout<<-1<<endl,0;
mx=max(mx,t.se);
}
}
int n1=(int)cv1.size()-1,n2=(int)cv2.size()-1;
ll ans=0;
v.eb(c,c,b,b,0);
for(auto&t:v)
t.p=lower_bound(all(cv1),t.p)-cv1.begin(),
t.q=lower_bound(all(cv1),t.q+1)-cv1.begin()-1,
t.r=lower_bound(all(cv2),t.r)-cv2.begin(),
t.s=lower_bound(all(cv2),t.s+1)-cv2.begin()-1;
for(int i=0;i<n;i++)
{
auto&t=v[i];
stdog.upd(1,0,n1,t.p,t.q,i);
stcat.upd(1,0,n2,t.r,t.s,i);
}
chk[n]=1;
priority_queue<event>pq;
pq.ep(0,v[n].p,v[n].q,0);
stmd.init(1,0,n1);
stmc.init(1,0,n2);
while(!pq.empty())
{
event cur=pq.top();
if(cur.cd==0)
{
int cid=stmd.query(1,0,n1,cur.l,cur.r);
if(cid!=inf)
{
if(!visd[cid])
{
visd[cid]=1;
vector<int>getv;
ans+=cur.h;
stdog.query(1,0,n1,cid,getv);
for(int&t:getv)
{
if(chk[t])
continue;
chk[t]=1;
pq.ep(v[t].t,v[t].p,v[t].q,0);
pq.ep(v[t].t,v[t].r,v[t].s,1);
}
}
else
stmd.del(1,0,n1,cid),ans+=(ll)cur.h*(cv1[cid+1]-cv1[cid]-1);
}
else
pq.pop();
}
else
{
int cid=stmc.query(1,0,n2,cur.l,cur.r);
if(cid!=inf)
{
if(!visc[cid])
{
visc[cid]=1;
ans+=cur.h;
vector<int>getv;
stcat.query(1,0,n2,cid,getv);
for(int&t:getv)
{
if(chk[t])
continue;
chk[t]=1;
pq.ep(v[t].t,v[t].p,v[t].q,0);
pq.ep(v[t].t,v[t].r,v[t].s,1);
}
}
else
stmc.del(1,0,n2,cid),ans+=(ll)cur.h*(cv2[cid+1]-cv2[cid]-1);
}
else
pq.pop();
}
}
for(int i=0;i<n;i++)
if(!chk[i])
return cout<<-1<<endl,0;
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
37992 KB |
Output is correct |
| 2 |
Correct |
26 ms |
38016 KB |
Output is correct |
| 3 |
Correct |
26 ms |
38016 KB |
Output is correct |
| 4 |
Correct |
27 ms |
37888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
38016 KB |
Output is correct |
| 2 |
Correct |
27 ms |
38048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
38392 KB |
Output is correct |
| 2 |
Correct |
29 ms |
38272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
38656 KB |
Output is correct |
| 2 |
Correct |
38 ms |
38520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
38656 KB |
Output is correct |
| 2 |
Correct |
36 ms |
38520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1271 ms |
77500 KB |
Output is correct |
| 2 |
Correct |
274 ms |
49088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1281 ms |
80316 KB |
Output is correct |
| 2 |
Correct |
828 ms |
77500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1269 ms |
77632 KB |
Output is correct |
| 2 |
Correct |
280 ms |
49132 KB |
Output is correct |
| 3 |
Correct |
655 ms |
61376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1208 ms |
75972 KB |
Output is correct |
| 2 |
Correct |
838 ms |
77504 KB |
Output is correct |
| 3 |
Correct |
594 ms |
59072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
49096 KB |
Output is correct |
| 2 |
Correct |
1075 ms |
74944 KB |
Output is correct |
| 3 |
Correct |
1250 ms |
76184 KB |
Output is correct |
