Submission #379055

#	Time	Username	Problem	Language	Result	Execution time	Memory
379055		FatihSolak	Plahte (COCI17_plahte)	C++17	160 / 160	1988 ms	295780 KiB

plahte

#include <bits/stdc++.h>
#define N 80005
#define M 1000000
#define INF 2000000000000000005ll
using namespace std;
long long dep[N];
long long ans[N];
long long par[N];
long long pr[N];
set<long long> col[N];
vector<long long> de[N];
map<long long,long long> cmp;
map<long long,long long> rel;
multiset<pair<long long,pair<long long,long long>>> t[M*4];
struct Node{
    long long a,b,c,d,pos;
    bool operator < (const Node other)const{
        if(a == other.a){
            return 1ll*(c-a)*(rel[d]-rel[b]) >= 1ll*(other.c-other.a)*(rel[other.d]-rel[other.b]);
        }
        return a < other.a;
    }
};
void upd(long long v,long long tl,long long tr,long long l,long long r,long long val1,long long val2,long long val3,long long ok){
    if(tr < l || r < tl){
        return;
    }
    if(l <= tl && tr <= r){
        if(ok){
            assert(t[v].count({val1,{val2,val3}}));
            t[v].erase(t[v].find({val1,{val2,val3}}));
        }
        else{
            t[v].insert({val1,{val2,val3}});
        }
        return;
    }
    long long tm = (tl+tr)/2;
    upd(v*2,tl,tm,l,r,val1,val2,val3,ok);
    upd(v*2+1,tm+1,tr,l,r,val1,val2,val3,ok);
}
pair<long long,pair<long long,long long>> get(long long v,long long l,long long r,long long pos){
    long long m = (l+r)/2;
    if(l == r){
        if(t[v].empty()){
            return make_pair(INF,make_pair(INF,INF));
        }
        return *t[v].begin();
    }
    if(pos<=m){
        if(t[v].empty()){
            return min(make_pair(INF,make_pair(INF,INF)),get(v*2,l,m,pos));
        }
        return min(*t[v].begin(),get(v*2,l,m,pos));
    }
    else{
        if(t[v].empty()){
            return min(make_pair(INF,make_pair(INF,INF)),get(v*2+1,m+1,r,pos));
        }
        return min(*t[v].begin(),get(v*2+1,m+1,r,pos));
    }
}
void go_par(long long v){
    ans[v] = col[pr[v]].size();
    if(par[v] == -1){
        return;
    }
    if(col[pr[v]].size() > col[pr[par[v]]].size()){
        for(auto u:col[pr[par[v]]]){
            col[pr[v]].insert(u);
        }
        pr[par[v]] = pr[v];
    }
    else{
        for(auto u:col[pr[v]]){
            col[pr[par[v]]].insert(u);
        }
    }
}
void solve(){
    long long n,m;
    cin >> n >> m;
    vector<Node> v;
    vector<long long> compress;
    for(long long i = 0;i<n;i++){
        long long a,b,c,d;
        cin >> a >> b >> c >> d;
        v.push_back({a,b,c,d,i});
        compress.push_back(b);
        compress.push_back(d);
    }
    vector<pair<long long,pair<long long,long long>>> v2;
    for(long long i=0;i<m;i++){
        long long a,b,c;
        cin >> a >> b >> c;
        v2.push_back({a,{b,c}});
        compress.push_back(b);
    }
    sort(compress.begin(),compress.end());
    long long cm = 1;
    for(long long i = 0;i<compress.size();i++){
        if(rel[cm-1] != compress[i]){
            cmp[compress[i]] = cm;
            rel[cm] = compress[i];
            cm++;
        }
    }
    assert(M > cm);
    for(auto &u:v){
        u.b = cmp[u.b];
        u.d = cmp[u.d];
    }
    for(auto &u:v2){
        u.second.first = cmp[u.second.first];
    }
    sort(v2.begin(),v2.end());
    sort(v.begin(),v.end());
    set<pair<long long,Node>> s;
    for(auto u:v){
        //cout << u.a << " " << u.b  << " " << u.c << " " << u.d<< endl;
        while(s.size() && s.begin()->first < u.a){
            auto k = s.begin()->second;
            s.erase(s.begin());
            upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,1);
        }
        auto k = get(1,1,M,u.b);
        if(k.first == INF){
            par[u.pos] = -1;
        }
        else{
            dep[u.pos] = dep[k.second.second] - 1;
            par[u.pos] = k.second.second;
        }
        s.insert({u.c,u});
        upd(1,1,M,u.b,u.d,1ll*(u.c-u.a)*(rel[u.d]-rel[u.b]) ,dep[u.pos],u.pos,0);
    }
    for(long long i=0;i<M*4;i++){
        t[i].clear();
    }
    s.clear();
    long long cnt = 0;
    for(auto u:v2){
        while(cnt != n && v[cnt].a <= u.first){
            auto k = v[cnt];
            upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,0);
            s.insert({k.c,k});
            cnt++;
        }
        while(s.size() && s.begin()->first < u.first){
            auto k = s.begin()->second;
            s.erase(s.begin());
            upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,1);
        }
        auto k = get(1,1,M,u.second.first);
        if(k.first == INF){
            continue;
        }
        else{
            col[k.second.second].insert(u.second.second);
        }
    }
    for(long long i=0;i<n;i++){
        dep[i] = -1*dep[i];
        pr[i] = i;
        de[dep[i]].push_back(i);
    }
    for(long long i=n;i>=0;i--){
        for(auto u:de[i]){
            go_par(u);
        }
    }
    for(long long i=0;i<n;i++){
        cout << ans[i] << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

plahte.cpp: In function 'void solve()':
plahte.cpp:101:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(long long i = 0;i<compress.size();i++){
      |                         ~^~~~~~~~~~~~~~~~

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