oj.uz

Submission #1110274

# Submission time Handle Problem Language Result Execution time Memory
1110274 2024-11-09T04:11:50 Z doducanh Plahte (COCI17_plahte) C++14
96 / 160
 270 ms 42836 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]=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],0,i});
        event.push_back({c[i],d[i],1,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],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++){
        if(event[i].type==0){
            int u=square[event[i].id-1].y1;
            int v=square[event[i].id-1].y2;
            par[event[i].id]=get(1,1,(int)v1.size(),u);
//            cout<<event[i].type<<" "<<par[event[i].id]<<" "<<event[i].id<<"\n";
            up(1,1,(int)v1.size(),u,v,event[i].id);
//            cout<<u<<" "<<v<<"\n";
//            cout<<get(1,1,(int)v1.size(),2)<<"\n";
        }
        else if(event[i].type==1){
            int u=square[event[i].id-1].y1;
            int v=square[event[i].id-1].y2;
//            cout<<event[i].type<<" "<<u<<" "<<v<<"\n";
            up(1,1,(int)v1.size(),u,v,par[event[i].id]);
        }
        else{
            int x=get(1,1,(int)v1.size(),event[i].y);
//            cout<<8<<" "<<event[i].y<<" "<<x<<"\n";
            if(x==0)continue;
            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);
    }
    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:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<event.size();i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 22680 KB Output is correct
2 Correct 79 ms 24216 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 23716 KB Output is correct
2 Correct 105 ms 23192 KB Output is correct
3 Incorrect 2 ms 10576 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 160 ms 36172 KB Output is correct
2 Correct 154 ms 27416 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 42836 KB Output is correct
2 Correct 263 ms 36120 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 38592 KB Output is correct
2 Correct 245 ms 35500 KB Output is correct
3 Incorrect 3 ms 10744 KB Output isn't correct
4 Halted 0 ms 0 KB -