oj.uz

Submission #499313

# Submission time Handle Problem Language Result Execution time Memory
499313 2021-12-28T01:59:55 Z julian33 Plahte (COCI17_plahte) C++14
0 / 160
 1959 ms 168652 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#ifdef LOCAL
const int mxN=100;
#else
const int mxN=3e5+5; //make sure this is right
#endif
const int mod=1e9+7;

struct RANK{
    vector<int> all;
    int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
    void add(int x){all.pb(x);}
    void fix(){
        sort(all.begin(),all.end());
        all.resize(unique(all.begin(),all.end())-all.begin());
    }  
} rnk;

set<pii> st[4*mxN];

void update(int v,int l,int r,int ind,pii val,int t){
    if(l>ind || r<ind) return;
    if(t) st[v].insert(val);
    else if(st[v].count(val)) st[v].erase(val);
    if(l==r) return;
    int m=(l+r)>>1;
    update(v<<1,l,m,ind,val,t);
    update(v<<1|1,m+1,r,ind,val,t);
}

pii query(int v,int l,int r,int lq,int rq,int lo,int hi){
    // deb(l,r);
    if(lq>rq) return {-1,-1};
    if(l>=lq && r<=rq){
        // deb(sz(st[v]),l,r,lq,rq,lo,hi);
        if(!sz(st[v])) return {-1,-1};
        if(st[v].rbegin()->first<lo) return {-1,-1};
        if(st[v].begin()->first>hi) return {-1,-1};
        return *st[v].lower_bound(pii(lo,hi));
    }
    int m=(l+r)>>1;
    return max(query(v<<1,l,m,lq,min(rq,m),lo,hi),query(v<<1|1,m+1,r,max(lq,m+1),rq,lo,hi));
}

struct rect{
    ll a,b,c,d,i;
};

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

vector<int> graph[mxN];
set<int> col[mxN];
int ans[mxN];

void dfs(int at){
    for(int &i:graph[at]){
        dfs(i);
        if(sz(col[i])>sz(col[at])) swap(col[i],col[at]);
        for(int j:col[i])
            col[at].insert(j);
        col[i].clear();
    }
    ans[at]=sz(col[at]);
}

map<pii,vector<int>> mp;

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n,m; cin>>n>>m;
    vector<rect> all,ori;
    vector<paint> off;
    for(int i=0;i<n;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        rnk.add(a); rnk.add(c);
        all.pb({a,b,c,d,i});
        ori.pb({a,b,c,d,i});
    }
    for(int i=0;i<m;i++){
        int x,y,k; cin>>x>>y>>k;
        rnk.add(x);
        off.pb({x,y,k});
    }
    rnk.fix();
    sort(all.begin(),all.end(),[&](auto x,auto y){return (x.c-x.a)*(x.d-x.b)<(y.c-y.a)*(y.d-y.b);});
    int N=sz(rnk.all);
    // assert(sz(rnk.all)<mxN);
    for(auto &[a,b,c,d,i]:all){
        // deb(a,b,c,d,i);
        a=rnk.get(a);
        c=rnk.get(c);
        pii res;
        while(1){
            res=query(1,1,N,a,c,b,d);
            if(res==pii(-1,-1)) break;
            // deb(res.first,res.second);
            graph[min(i,(ll)res.second)].pb(max(i,(ll)res.second));
            update(1,1,N,rnk.get(ori[res.second].a),res,0);
        }
        update(1,1,N,a,{b,i},1);
    }
    for(int i=1;i<=4*N;i++)
        st[i].clear();
    for(auto &[x,y,k]:off){
        x=rnk.get(x);
        update(1,1,N,x,{y,k},1);
        mp[{y,k}].pb(x);
    }
    sort(all.begin(),all.end(),[&](auto x,auto y){return x.i>y.i;});
    for(auto &[a,b,c,d,i]:all){
        pii res;
        // deb(a,b,c,d,i);
        while(1){
            res=query(1,1,N,a,c,b,d);
            if(res==pii(-1,-1)) break;
            // deb(res.first,res.second);
            if(sz(mp[res])){
                col[i].insert(res.second);
                int x=mp[res].back();
                mp[res].pop_back();
                update(1,1,N,x,res,0);
            } else break;
        }
    }
    memset(ans,-1,sizeof(ans));
    for(int i=0;i<n;i++){
        if(ans[i]==-1) dfs(i);
        cout<<ans[i]<<"\n";
    }
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:124:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for(auto &[a,b,c,d,i]:all){
      |               ^
plahte.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |     for(auto &[x,y,k]:off){
      |               ^
plahte.cpp:146:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |     for(auto &[a,b,c,d,i]:all){
      |               ^

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 587 ms 113732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 549 ms 110540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 990 ms 133464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1790 ms 168500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1959 ms 168652 KB Output isn't correct
2 Halted 0 ms 0 KB -