| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330726 |
2020-11-26T12:00:16 Z |
tzxydby |
Plahte (COCI17_plahte) |
C++11 |
|
999 ms |
333400 KB |
#include<bits/stdc++.h>
using namespace std;
const int N=80005,M=30000000;
struct sq
{
int x1,x2,y1,y2,id;
bool operator<(const sq &k)const
{
return 1ll*(x2-x1)*(y2-y1)>1ll*(k.x2-k.x1)*(k.y2-k.y1);
}
}a[N];
int n,m,sz,sx,sy,mx[M],lc[M],rc[M],qx[N],qy[N],qt[N],ans[N],vis[N];
vector<int>vx,vy,e[N];
set<int>s[N];
struct seg
{
int rt;
int xd()
{
sz++;
return sz;
}
void update(int &k,int l,int r,int a,int b,int v)
{
if(!k) k=xd();
if(l==a&&r==b)
{
mx[k]=max(mx[k],v);
return;
}
int mid=l+r>>1;
if(b<=mid) update(lc[k],l,mid,a,b,v);
else if(a>mid) update(rc[k],mid+1,r,a,b,v);
else update(lc[k],l,mid,a,mid,v),update(rc[k],mid+1,r,mid+1,b,v);
}
int gmax(int k,int l,int r,int x)
{
if(!k) return 0;
if(l==r) return mx[k];
int mid=l+r>>1;
if(x<=mid) return max(mx[k],gmax(lc[k],l,mid,x));
else return max(mx[k],gmax(rc[k],mid+1,r,x));
}
}tr[N<<2];
void build(int k,int l,int r)
{
tr[k].rt=tr[k].xd();
if(l==r)
return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int a,int b,int a2,int b2,int v)
{
if(l==a&&r==b)
{
tr[k].update(tr[k].rt,1,sy,a2,b2,v);
return;
}
int mid=l+r>>1;
if(b<=mid) update(k<<1,l,mid,a,b,a2,b2,v);
else if(a>mid) update(k<<1|1,mid+1,r,a,b,a2,b2,v);
else update(k<<1,l,mid,a,mid,a2,b2,v),update(k<<1|1,mid+1,r,mid+1,b,a2,b2,v);
}
int qmax(int k,int l,int r,int x,int y)
{
if(l==r)
return tr[k].gmax(tr[k].rt,1,sy,y);
int mid=l+r>>1;
if(x<=mid) return max(tr[k].gmax(tr[k].rt,1,sy,y),qmax(k<<1,l,mid,x,y));
else return max(tr[k].gmax(tr[k].rt,1,sy,y),qmax(k<<1|1,mid+1,r,x,y));
}
void dfs(int u)
{
vis[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
dfs(v);
if(s[u].size()<s[v].size())
s[u].swap(s[v]);
for(set<int>::iterator it=s[v].begin();it!=s[v].end();it++)
s[u].insert(*it);
}
ans[a[u].id]=s[u].size();
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
a[i].id=i;
vx.push_back(a[i].x1),vx.push_back(a[i].x2);
vy.push_back(a[i].y1),vy.push_back(a[i].y2);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&qx[i],&qy[i],&qt[i]);
vx.push_back(qx[i]);
vy.push_back(qy[i]);
}
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
sx=vx.size();
sort(vy.begin(),vy.end());
vy.erase(unique(vy.begin(),vy.end()),vy.end());
sy=vy.size();
for(int i=1;i<=n;i++)
{
a[i].x1=lower_bound(vx.begin(),vx.end(),a[i].x1)-vx.begin()+1;
a[i].x2=lower_bound(vx.begin(),vx.end(),a[i].x2)-vx.begin()+1;
a[i].y1=lower_bound(vy.begin(),vy.end(),a[i].y1)-vy.begin()+1;
a[i].y2=lower_bound(vy.begin(),vy.end(),a[i].y2)-vy.begin()+1;
}
sort(a+1,a+n+1);
build(1,1,sx);
for(int i=1;i<=n;i++)
{
int f=qmax(1,1,sx,a[i].x1,a[i].y1);
if(f)
e[f].push_back(i);
update(1,1,sx,a[i].x1,a[i].x2,a[i].y1,a[i].y2,i);
}
for(int i=1;i<=m;i++)
{
qx[i]=lower_bound(vx.begin(),vx.end(),qx[i])-vx.begin()+1;
qy[i]=lower_bound(vy.begin(),vy.end(),qy[i])-vy.begin()+1;
int f=qmax(1,1,sx,qx[i],qy[i]);
if(f)
s[f].insert(qt[i]);
}
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
Compilation message
plahte.cpp: In member function 'void seg::update(int&, int, int, int, int, int)':
plahte.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int mid=l+r>>1;
| ~^~
plahte.cpp: In member function 'int seg::gmax(int, int, int, int)':
plahte.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid=l+r>>1;
| ~^~
plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid=l+r>>1;
| ~^~
plahte.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
plahte.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid=l+r>>1;
| ~^~
plahte.cpp: In function 'int qmax(int, int, int, int, int)':
plahte.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid=l+r>>1;
| ~^~
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<e[u].size();i++)
| ~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
plahte.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%d%d%d",&qx[i],&qy[i],&qt[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
49120 KB |
Output is correct |
| 2 |
Correct |
294 ms |
57696 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
318 ms |
61152 KB |
Output is correct |
| 2 |
Correct |
381 ms |
69728 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
591 ms |
194904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
992 ms |
333400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
999 ms |
316372 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
