Submission #714664

#	Time	Username	Problem	Language	Result	Execution time	Memory
714664		fuad27	Plahte (COCI17_plahte)	C++17	160 / 160	1022 ms	267028 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
struct rect {
  int a, b, c, d, idx;
};
struct point {
  int x, y, c;
};
const int N = 8*8e4+10;
priority_queue<pair<int,int>> T[2*N];
void build() {
	for(int i =2*N-1;i>0;i--){
    T[i].push({-1,0});
  }
}
void add(int l, int r, int l1, int id) {
  r++;
  for(l+=N,r+=N;l<r;l>>=1,r>>=1){
    if(l&1) {
      T[l++].push({l1,id});
    }
    if(r&1) {
      T[--r].push({l1,id});
    }
  }
}
void rem(int l, int r) {
  r++;
  for(l+=N,r+=N;l<r;l>>=1,r>>=1){
    if(l&1) {
      T[l++].pop();
    }
    if(r&1) {
      T[--r].pop();
    }
  }
}
int query(int p) {
  pair<int,int> res={-1,0};
  for(p+=N;p>0;p>>=1)res=max(T[p].top(),res);
  return res.second;
}
vector<int> child[N];
set<int> res[N];
int sz[N];
void dfs(int at) {
  dbg(at,child[at]);
  for(int to:child[at]) {
    dfs(to);
    if(res[to].size()>res[at].size()) {
      swap(res[to], res[at]);
    }
    res[at].insert(res[to].begin(),res[to].end());
  }
  sz[at]=res[at].size();
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  build();
  rect r[n];
  point p[m];
  map<int,int> cc;
  for(int i = 0;i<n;i++){
    cin >> r[i].a >> r[i].b >> r[i].c >> r[i].d;
    cc[r[i].a]=cc[r[i].b]=cc[r[i].c]=cc[r[i].d]=1;
    r[i].idx=i+1;
  }
  for(int i = 0;i<m;i++){
    cin>>p[i].x>>p[i].y>>p[i].c;
    cc[p[i].x]=cc[p[i].y]=1;
  }
  vector<int> on[2*N], off[2*N];
  vector<int> po[2*N];
  {
    int cnt=0;
    for(auto &i:cc) {
      i.second=cnt++;
    }
    for(int i = 0;i<n;i++) {
      r[i].a=cc[r[i].a];
      r[i].b=cc[r[i].b];
      r[i].c=cc[r[i].c];
      r[i].d=cc[r[i].d];
    }
    for(int i = 0;i<m;i++){
      p[i].x=cc[p[i].x];
      p[i].y=cc[p[i].y];
    }
  }
  for(int i = 0;i<n;i++) {
    dbg(r[i].a, r[i].b, r[i].c, r[i].d);
    on[r[i].a].push_back(i);
    off[r[i].c].push_back(i);
  }
  for(int i = 0;i<m;i++) {
    dbg(p[i].x,p[i].y);
    po[p[i].x].push_back(i);
  }
  for(int i = 0;i<2*N;i++) {
    for(int to:on[i]) {
      child[query(r[to].b)].push_back(r[to].idx);
      add(r[to].b, r[to].d, i, r[to].idx);
    }
    for(int to:po[i]) {
      dbg(query(p[to].y));
      res[query(p[to].y)].insert(p[to].c);
    }
    for(int to:off[i]) {
      rem(r[to].b, r[to].d);
    }
  }
  dfs(0);
  for(int i=1;i<=n;i++)cout << sz[i] << "\n";
}

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