oj.uz

답안 #1110259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110259 2024-11-09T03:47:06 Z doducanh Plahte (COCI17_plahte) C++14
0 / 160
 272 ms 35048 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);
    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]!=0){
        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)
{
    for(int v:adj[u])if(v!=par){
        dfs(v,u);
        if(dp[u].size()<dp[v].size())swap(u,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;
    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++){
        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)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;
            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);
            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:120:18: 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++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 16400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 18196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 173 ms 29476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 272 ms 35048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 268 ms 31624 KB Output isn't correct
2 Halted 0 ms 0 KB -