oj.uz

Submission #714662

# Submission time Handle Problem Language Result Execution time Memory
714662 2023-03-25T07:30:34 Z fuad27 Plahte (COCI17_plahte) C++17
96 / 160
 1099 ms 281988 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 = 4*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 255 ms 121036 KB Output is correct
2 Correct 296 ms 121164 KB Output is correct
3 Correct 74 ms 108016 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 125832 KB Output is correct
2 Correct 382 ms 125404 KB Output is correct
3 Correct 74 ms 107948 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 139924 KB Output is correct
2 Correct 566 ms 134744 KB Output is correct
3 Correct 90 ms 108096 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 984 ms 281220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1099 ms 281988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -