oj.uz

Submission #714664

# Submission time Handle Problem Language Result Execution time Memory
714664 2023-03-25T07:31:03 Z fuad27 Plahte (COCI17_plahte) C++17
160 / 160
 1022 ms 267028 KB 
#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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 228956 KB Output is correct
2 Correct 312 ms 228900 KB Output is correct
3 Correct 149 ms 215644 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 233580 KB Output is correct
2 Correct 376 ms 231364 KB Output is correct
3 Correct 157 ms 215624 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 247840 KB Output is correct
2 Correct 644 ms 239392 KB Output is correct
3 Correct 157 ms 215768 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 267028 KB Output is correct
2 Correct 1022 ms 261132 KB Output is correct
3 Correct 159 ms 215696 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 263796 KB Output is correct
2 Correct 924 ms 255952 KB Output is correct
3 Correct 151 ms 215720 KB Output is correct