oj.uz

Submission #1110251

# Submission time Handle Problem Language Result Execution time Memory
1110251 2024-11-09T03:31:25 Z doducanh Plahte (COCI17_plahte) C++14
96 / 160
 308 ms 74128 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[10000005];
int laz[10000005];
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++){
//        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++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 56084 KB Output is correct
2 Correct 86 ms 58508 KB Output is correct
3 Correct 7 ms 49488 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 57876 KB Output is correct
2 Correct 102 ms 59152 KB Output is correct
3 Incorrect 6 ms 49488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 67732 KB Output is correct
2 Correct 161 ms 65424 KB Output is correct
3 Correct 6 ms 49488 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 74128 KB Output is correct
2 Correct 298 ms 68144 KB Output is correct
3 Correct 8 ms 49656 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 71464 KB Output is correct
2 Correct 294 ms 68772 KB Output is correct
3 Incorrect 8 ms 49744 KB Output isn't correct
4 Halted 0 ms 0 KB -