제출 #1279442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279442		escobrand	Plahte (COCI17_plahte)	C++20	0 / 160	175 ms	40112 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;
  bool operator < (const bruh & o)const 
  {
    if(lx != o.lx)return lx<o.lx;
    return ly<o.ly;
  }
};

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

struct lmao
{
  int ti,rx,id;
}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++] = {tt,rx,c};
    if(r&1)t[--r] = {tt,rx,c};
  }
}

int cal(int i,int rx)
{
  int mx = 0;
  int ans = 0;
  for(i+=maxn;i;i>>=1)
  {
    if(t[i].ti > mx && t[i].rx >= rx)
    {
      mx = t[i].ti;
      ans = t[i].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({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({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);
      }
    }
    
    dfs(0);
    
    for(int i = 1;i<=n;i++)cout<<ans[i]<<'\n';
    
    return 0;
}

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