| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1110249 |
2024-11-09T03:28:05 Z |
doducanh |
Plahte (COCI17_plahte) |
C++14 |
|
294 ms |
68752 KB |
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=8e4+7;
struct Point
{
int x,y,type,id;
};
struct hinhvuong
{
int x1,y1,x2,y2,id;
};
int t[4000005];
int laz[4000005];
void down(int id)
{
for(int i=lc;i<=rc;i++){
t[i]=laz[id];
laz[i]=laz[id];
}
laz[id]=-1;
}
void up(int id,int l,int r,int u,int v,int val)
{
if(l>v||r<u)return;
if(u<=l&&r<=v){
t[id]=val;
laz[id]=val;
return;
}
if(l!=r&&laz[id]!=-1){
down(id);
}
int m=(l+r)/2;
up(lc,l,m,u,v,val);
up(rc,m+1,r,u,v,val);
t[id]=max(t[lc],t[rc]);
}
int get(int id,int l,int r,int u,int v)
{
if(l>v||r<u)return 0;
if(u<=l&&r<=v){
return t[id];
}
if(l!=r&&laz[id]!=-1){
down(id);
}
int m=(l+r)/2;
return max(get(lc,l,m,u,v),get(rc,m+1,r,u,v));
}
vector<int>adj[maxn];
int par[maxn];
int a[maxn];
int b[maxn];
int c[maxn],d[maxn],x[maxn],y[maxn],k[maxn];
set<int>dp[maxn];
int n,m;
int Pos(vector<int>&v,int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int chiso[maxn];
int ans[maxn];
void dfs(int u,int par)
{
vector<int>tmp;
for(int v:adj[u])if(v!=par){
dfs(v,u);
if(dp[chiso[u]].size()>=dp[chiso[v]].size()){
for(int x:dp[chiso[v]]){
dp[chiso[u]].insert(x);
}
}
else{
for(int x:dp[chiso[u]]){
dp[chiso[v]].insert(x);
}
chiso[u]=chiso[v];
}
}
ans[u]=dp[chiso[u]].size();
}
void sol(void){
memset(laz,-1,sizeof(laz));
vector<hinhvuong>square;
vector<Point>event;
cin>>n>>m;
vector<int>v1;
vector<int>v2;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
v1.push_back(a[i]),v2.push_back(b[i]),v1.push_back(c[i]),v2.push_back(d[i]);
}
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i]>>k[i];
v1.push_back(x[i]);
v2.push_back(y[i]);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
v1.erase(unique(v1.begin(),v1.end()),v1.end());
v2.erase(unique(v2.begin(),v2.end()),v2.end());
for(int i=1;i<=n;i++){
a[i]=Pos(v1,a[i]),b[i]=Pos(v2,b[i]),c[i]=Pos(v1,c[i]),d[i]=Pos(v2,d[i]);
square.push_back({a[i],b[i],c[i],d[i],i});
event.push_back({a[i],b[i],0,i});
event.push_back({c[i],d[i],1,i});
}
for(int i=1;i<=m;i++){
int xx=Pos(v1,x[i]);
int yy=Pos(v2,y[i]);
event.push_back({xx,yy,2,k[i]});
}
sort(event.begin(),event.end(),[&](const Point &a,const Point &b){
return (a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.type>b.type));
});
for(int i=0;i<event.size();i++){
int u=square[event[i].id-1].y1;
int v=square[event[i].id-1].y2;
// cout<<event[i].x<<" "<<event[i].y<<" "<<event[i].type<<" "<<event[i].id<<"\n";
if(event[i].type==0){
int u=square[event[i].id-1].y1;
int v=square[event[i].id-1].y2;
// cout<<u<<" "<<v<<"\n";
par[event[i].id]=get(1,1,(int)v2.size(),u,v);
up(1,1,(int)v2.size(),u,v,event[i].id);
}
else if(event[i].type==1){
int u=square[event[i].id-1].y1;
int v=square[event[i].id-1].y2;
// cout<<u<<" "<<v<<"\n";
up(1,1,(int)v2.size(),u,v,par[event[i].id]);
}
else{
int x=get(1,1,(int)v2.size(),event[i].y,event[i].y);
// cout<<x<<"\n";
dp[x].insert(event[i].id);
}
}
for(int i=1;i<=n;i++)chiso[i]=i;
for(int i=1;i<=n;i++)if(par[i]!=0){
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
for(int i=1;i<=n;i++)if(par[i]==0){
dfs(i,0);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
plahte.cpp: In function 'void sol()':
plahte.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i=0;i<event.size();i++){
| ~^~~~~~~~~~~~~
plahte.cpp:130:13: warning: unused variable 'u' [-Wunused-variable]
130 | int u=square[event[i].id-1].y1;
| ^
plahte.cpp:131:13: warning: unused variable 'v' [-Wunused-variable]
131 | int v=square[event[i].id-1].y2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
56852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
61712 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
68752 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
294 ms |
50696 KB |
Output is correct |
| 2 |
Correct |
285 ms |
49536 KB |
Output is correct |
| 3 |
Correct |
4 ms |
24912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
47908 KB |
Output is correct |
| 2 |
Correct |
276 ms |
50196 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
24912 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
