Submission #1279542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279542		escobrand	Plahte (COCI17_plahte)	C++20	96 / 160	2097 ms	49836 KiB

plahte

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<int,int> pii;

const int maxn = 32e4+10;

int i,n,m;

struct bruh
{
  int lx,ly,rx,ry;
  int id;
  
  bruh():lx(0),rx(0),ly(0),ry(0),id(0){}
  bruh(int a,int b,int c,int d,int e):lx(a),ly(b),rx(c),ry(d),id(e){}
  bool operator < (const bruh & o)const 
  {
    if(lx != o.lx)return lx<o.lx;
    if(id != o.id)return id>o.id;
    return ly<o.ly;
  }
};

vector<int> comx,comy;
vector<bruh> v;

struct lmao
{
  int ti,rx,id;
  lmao():ti(0),rx(0),id(0){}
  lmao(int a,int b,int c):ti(a),rx(b),id(c){}
};
vector<lmao>t[maxn * 2];
int tt;
void up(int l,int r,int rx,int c)
{
  tt++;
  l += maxn;
  r += maxn + 1;
  for(;l<r;l>>=1,r>>=1)
  {
    if(l&1)t[l++].pb(lmao(tt,rx,c));
    if(r&1)t[--r].pb(lmao(tt,rx,c));
  }
}

int cal(int i,int rx)
{
  int mx = 0;
  int ans = 0;
  for(i+=maxn;i;i>>=1)
  {
    for(lmao & k : t[i])
    {
      if(k.ti > mx && k.rx >= rx)
    {
      mx = k.ti;
      ans = k.id;
    }
    }
  }
  return ans;
}

vector<int> adj[maxn];
set<int> s[maxn];
int ans[maxn];
void dfs(int i)
{
  for(int k : adj[i])
  {
    dfs(k);
    if(s[i].size()<s[k].size())swap(s[i],s[k]);
    for(int p : s[k])s[i].insert(p);
  }
  ans[i] = s[i].size();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    
    for(int i =1;i<=n;i++)
    {
      int lx,ly,rx,ry;
      cin>>lx>>ly>>rx>>ry;
      v.pb(bruh(lx,ly,rx,ry,i));
      comx.pb(lx);
      comx.pb(rx);
      comy.pb(ly);
      comy.pb(ry);
    }
    
    while(m--)
    {
      int x,y,c;
      cin>>x>>y>>c;
      // cout<<x<<' '<<y<<'\n';
      comx.pb(x);
      comy.pb(y);
      v.pb(bruh(x,y,c,0,0));
    }
    
    sort(all(comx));
    sort(all(comy));
    sort(all(v));
    
    for(bruh & k : v)
    {
      k.lx = upper_bound(all(comx),k.lx) - comx.begin();
      k.ly = upper_bound(all(comy),k.ly) - comy.begin();
      int p = cal(k.ly,k.lx);
      if(k.id)
      {
        k.rx = upper_bound(all(comx),k.rx) - comx.begin();
        k.ry = upper_bound(all(comy),k.ry) - comy.begin();
        adj[p].pb(k.id);
        up(k.ly,k.ry,k.rx,k.id);
      }
      else 
      {
        s[p].insert(k.rx);
      }
      // cout<<k.lx<<' '<<k.ly<<' '<<k.rx;
      // if(k.ry)cout<<' '<<k.ry<<' '<<k.id;
      // cout<<'\n';
      
    }
    
    dfs(0);
    
    for(int i = 1;i<=n;i++)cout<<ans[i]<<'\n';
    
    return 0;
}

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