| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1110288 |
2024-11-09T04:40:30 Z |
doducanh |
Plahte (COCI17_plahte) |
C++14 |
|
279 ms |
42512 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;
const int inf=1e9+7;
struct Point
{
int x,u,v,id;
bool operator<(const Point b) const {
if (x == b.x) {
if (id < 0) return 0;
if (b.id < 0) return 1;
return v < b.v;
}
return x < b.x;
}
};
struct hinhvuong
{
int x1,y1,x2,y2,id;
};
int t[20000005];
int laz[20000005];
void down(int id)
{
for(int i=lc;i<=rc;i++){
t[i]=t[id];
laz[i]=1;
}
laz[id]=0;
}
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]=1;
return;
}
if(l!=r&&laz[id]!=0){
down(id);
}
int m=(l+r)/2;
up(lc,l,m,u,v,val);
up(rc,m+1,r,u,v,val);
}
int get(int id,int l,int r,int u)
{
if(l!=r&&laz[id]!=0){
down(id);
}
if(l==r)return t[id];
int m=(l+r)/2;
if(u<=m)return get(lc,l,m,u);
else return get(rc,m+1,r,u);
}
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)
{
for(int v:adj[u])if(v!=par){
dfs(v,u);
if(dp[u].size()<dp[v].size())swap(dp[u],dp[v]);
for(int x:dp[v]){
dp[u].insert(x);
}
}
ans[u]=dp[u].size();
}
void sol(void){
vector<hinhvuong>square;
vector<Point>event;
cin>>n>>m;
vector<int>v1;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
v1.push_back(a[i]),v1.push_back(b[i]),v1.push_back(c[i]),v1.push_back(d[i]);
}
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i]>>k[i];
v1.push_back(x[i]);
v1.push_back(y[i]);
}
sort(v1.begin(),v1.end());
v1.erase(unique(v1.begin(),v1.end()),v1.end());
for(int i=1;i<=n;i++){
a[i]=Pos(v1,a[i]),b[i]=Pos(v1,b[i]),c[i]=Pos(v1,c[i]),d[i]=Pos(v1,d[i]);
square.push_back({a[i],b[i],c[i],d[i],i});
event.push_back({a[i],b[i],d[i],i});
event.push_back({c[i],b[i],d[i],-i});
}
for(int i=1;i<=m;i++){
x[i]=Pos(v1,x[i]);
y[i]=Pos(v1,y[i]);
event.push_back({x[i],y[i],inf,i});
}
sort(event.begin(),event.end());
for(int i=0; i<event.size(); i++)
{
auto tmp = event[i];
// cout<<tmp.x<<" "<<tmp.u<<" "<<tmp.v<<" "<<tmp.id<<"\n";
if (tmp.v == inf)
{
int x=get(1,1,(int)v1.size(),tmp.u);
dp[x].insert(k[tmp.id]);
continue;
}
if (tmp.id< 0)up(1,1,(int)v1.size(),tmp.u, tmp.v, par[-tmp.id]);
else
{
par[tmp.id] =get(1,1,(int)v1.size(),tmp.u);
up(1,1,(int)v1.size(),tmp.u, tmp.v,tmp.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);
}
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:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0; i<event.size(); i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
22444 KB |
Output is correct |
| 2 |
Correct |
78 ms |
22948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
23476 KB |
Output is correct |
| 2 |
Correct |
87 ms |
22952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
36124 KB |
Output is correct |
| 2 |
Correct |
145 ms |
27416 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
42512 KB |
Output is correct |
| 2 |
Correct |
254 ms |
36376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
261 ms |
38596 KB |
Output is correct |
| 2 |
Correct |
257 ms |
35872 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
