Submission #667929

#	Time	Username	Problem	Language	Result	Execution time	Memory
667929		slo	Plahte (COCI17_plahte)	C++14	160 / 160	483 ms	379372 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))

typedef long long ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps=1e-9;
        if(x+eps<y){
            x=y; return true;
        }
        return false;
    }

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps=1e-9;
        if(x>y+eps){
            x=y; return true;
        }
        return false;
    }

/*-----------------MAIN PROGRAM-----------------*/

const int N=1e5+7;
const int offset=(1<<18);

struct Rec{
    int x1=0, y1=0, x2=0, y2=0;
};

struct Ball{
    int x, y, k;
};

struct SegTree{
    stack<pii> seg[offset<<1];
    void add(int i, int l, int r, int u, int v, pii val){
        if(v<l || r<u) return;
        if(u<=l && r<=v){
            seg[i].push(val);
            return;
        }
        int m=(l+r)>>1, k=i<<1;
        add(k,l,m,u,v,val);
        add(k+1,m+1,r,u,v,val);
    }
    void add(int l, int r, pii val){
        add(1,0,offset-1,l,r,val);
    }
    void remv(int i, int l, int r, int u, int v){
        if(v<l || r<u) return;
        if(u<=l && r<=v){
            seg[i].pop();
            return;
        }
        int m=(l+r)>>1, k=i<<1;
        remv(k,l,m,u,v);
        remv(k+1,m+1,r,u,v);
    }
    void remv(int l, int r){
        remv(1,0,offset-1,l,r);
    }
    int calc(int node){
        node+=offset;
        int latest=-1, res=-1;
        while(node){
            if(!seg[node].empty() &&
                maximize(latest,seg[node].top().fi))
                    res=seg[node].top().se;
            node/=2;
        }
        return res;
    }
} ds;

int n, m;
Rec rec[N];
Ball ball[N];
vi adj[N];
int par[N], ans[N];
set<int> color[N];

void read(){
    cin>>n>>m;
    rep(i,n)
        cin>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2;
    rep(i,m)
        cin>>ball[i].x>>ball[i].y>>ball[i].k;
}

void hashing(){
    vi v;
    rep(i,n) v.pb(rec[i].y1), v.pb(rec[i].y2);
    rep(i,m) v.pb(ball[i].y);
    sort(all(v));
    v.resize(unique(all(v))-v.begin());
    rep(i,n){
        rec[i].y1=lower_bound(all(v),rec[i].y1)-v.begin();
        rec[i].y2=lower_bound(all(v),rec[i].y2)-v.begin();
    }
    rep(i,m)
        ball[i].y=lower_bound(all(v),ball[i].y)-v.begin();
}

void sweep(){
    vector<pair<pii,pii> > evt;
    rep(i,n){
        evt.pb(mp(mp(rec[i].x1,i+1),mp(rec[i].y1,rec[i].y2)));
        evt.pb(mp(mp(rec[i].x2+1,-(i+1)),mp(rec[i].y1,rec[i].y2)));
    }
    rep(i,m)
        evt.pb(mp(mp(ball[i].x,N),mp(ball[i].y,i)));
    sort(all(evt));

    rep(i,n) par[i]=i;

    rep(i,sz(evt))
        if(evt[i].fi.se==N){ // paintball
            int recId=ds.calc(evt[i].se.fi);
            if(recId!=-1)
                color[recId].ins(ball[evt[i].se.se].k);
        }
        else if(evt[i].fi.se>0){ // add rec
            int curRecId=evt[i].fi.se-1;
            int recId=ds.calc(evt[i].se.se);
            if(recId!=-1){
                par[curRecId]=recId;
                adj[recId].pb(curRecId);
                //cout<<recId+1<<' '<<curRecId+1<<'\n';
            }
            ds.add(evt[i].se.fi,evt[i].se.se,mp(i,curRecId));
        }
        else // remove rec
            ds.remv(evt[i].se.fi,evt[i].se.se);
}

void mergeSet(int u, int v){
    if(sz(color[u])<sz(color[v]))
        swap(color[u],color[v]);
    for(int c:color[v]) color[u].ins(c);
}

void dfs(int u){
    for(int v:adj[u]){
        dfs(v);
        mergeSet(u,v);
    }
    ans[u]=sz(color[u]);
}

void solve(){
    rep(i,n) if(par[i]==i) dfs(i);
    rep(i,n) cout<<ans[i]<<'\n';
}

int main(){
    fastIO;
    read();
    hashing();
    sweep();
    solve();
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void sweep()':
plahte.cpp:5:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forw(i,l,r) for(int i=l; i<r; i++)
      |                                   ^
plahte.cpp:8:18: note: in expansion of macro 'forw'
    8 | #define rep(i,n) forw(i,0,n)
      |                  ^~~~
plahte.cpp:148:5: note: in expansion of macro 'rep'
  148 |     rep(i,sz(evt))
      |     ^~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32