oj.uz

Submission #726675

# Submission time Handle Problem Language Result Execution time Memory
726675 2023-04-19T08:58:09 Z vjudge1 Plahte (COCI17_plahte) C++17
160 / 160
 496 ms 32320 KB 
#include <bits/stdc++.h>
using namespace std;
 
 
#define f first
#define s second
 
 struct Rect{
  int a,b,c,d,id;
};
 
signed main(){
  int N,M;
  cin >> N >> M;
  vector<Rect> rect;
  for(int i = 0; i < N; ++i){
    Rect R;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    R.a=a,R.b=b,R.c=c,R.d=d,R.id=i;
    rect.push_back(R);
  }
 
  vector<int> par(N,-1);
 
  {
    vector<pair<int,int>> events;
    for(int i = 0; i < N; ++i){
      events.emplace_back(i,+1);
      events.emplace_back(i,-1);
    }
 
    sort(events.begin(),events.end(),[&](auto l,auto r){
      if(l.f == r.f)
        return l.s > r.s;
      if(l.s == 1 && r.s == 1)
        return (rect[l.f].a == rect[r.f].a ? rect[l.f].b < rect[r.f].b : rect[l.f].a < rect[r.f].a);
      if(l.s == 1 && r.s == -1)
        return (rect[l.f].a == rect[r.f].c ? true : rect[l.f].a < rect[r.f].c);
      if(l.s == -1 && r.s == 1)
        return (rect[l.f].c == rect[r.f].a ? false : rect[l.f].c < rect[r.f].a);
      if(l.s == -1 && r.s == -1)
        return (rect[l.f].c == rect[r.f].c ? rect[l.f].d > rect[r.f].d : rect[l.f].c < rect[r.f].c);
    });
 
    set<array<int,3>> s;
 
    for(auto [i,t] : events){
      if(t < 0){
        s.erase(s.find({rect[i].b,i,-1}));
        s.erase(s.find({rect[i].d,i,+1}));
      }else{
        s.insert({rect[i].b,i,-1});
        s.insert({rect[i].d,i,+1});
        auto itr = s.find({{rect[i].b,i,-1}});
        if(itr != s.begin()){
          --itr;
          if((*itr)[2] < 0)
            par[i] = (*itr)[1];
          else
            par[i] = par[(*itr)[1]];
        }
      }
    }
  }
 
  vector<int> x(M),y(M),k(M);
  for(int i = 0; i < M; ++i)
    cin >> x[i] >> y[i] >> k[i];
 
  vector<set<int>> have(N);
 
  {
 
    vector<pair<int,int>> events;
    for(int i = 0; i < N; ++i){
      events.emplace_back(i,+1);
      events.emplace_back(i,-1);
    }
    for(int i = 0; i < M; ++i){
      events.emplace_back(i,0);
    }
 
    sort(events.begin(),events.end(),[&](auto l,auto r){
      if(l.s != 0 && r.s != 0){
        if(l.f == r.f)
          return l.s > r.s;
        if(l.s == 1 && r.s == 1)
          return (rect[l.f].a == rect[r.f].a ? rect[l.f].b < rect[r.f].b : rect[l.f].a < rect[r.f].a);
        if(l.s == 1 && r.s == -1)
          return (rect[l.f].a == rect[r.f].c ? true : rect[l.f].a < rect[r.f].c);
        if(l.s == -1 && r.s == 1)
          return (rect[l.f].c == rect[r.f].a ? false : rect[l.f].c < rect[r.f].a);
        if(l.s == -1 && r.s == -1)
          return (rect[l.f].c == rect[r.f].c ? rect[l.f].d > rect[r.f].d : rect[l.f].c < rect[r.f].c);
      }else{
        if(l.s != 0)
          return (l.s>0?rect[l.f].a<=x[r.f]:rect[l.f].c<x[r.f]);
        if(r.s != 0)
          return (r.s>0?x[l.f]<rect[r.f].a:x[l.f]<=rect[r.f].c);
        return x[l.f] < x[r.f];
      }
    });
 
    set<array<int,3>> s;
 
    for(auto [i,t] : events){
      if(t < 0){
        s.erase(s.find({rect[i].b,i,-1}));
        s.erase(s.find({rect[i].d,i,+1}));
      }else if(t == 0){
        auto itr = s.lower_bound({y[i],-1,-1});
        if(itr != s.end()){
          if((*itr)[2] > 0 || y[i] == rect[(*itr)[1]].b){
            have[(*itr)[1]].insert(k[i]);
          }else{
            if(par[(*itr)[1]] >= 0){
              have[par[(*itr)[1]]].insert(k[i]);
            }
          }
        }
      }else{
        s.insert({rect[i].b,i,-1});
        s.insert({rect[i].d,i,+1});
      }
    }
  }
 
  vector<int> g[N];
 
  for(int i = 0; i < N; ++i)
    if(par[i] >= 0)
      g[par[i]].push_back(i);
 
  vector<int> ans(N);
 
  function<void(int)> dfs = [&](int i) -> void {
    for(auto j : g[i]){
      dfs(j);
      if(have[i].size() < have[j].size())
        have[i].swap(have[j]);
      for(auto x : have[j])
        have[i].insert(x);
      have[j].clear();
    }
    ans[i] = have[i].size();
  };
 
  for(int i = 0; i < N; ++i)
    if(par[i] < 0)
      dfs(i);
 
  for(auto i : ans)
    cout << i << "\n";
 
 
  
  return 0;
}

Compilation message

plahte.cpp: In lambda function:
plahte.cpp:44:5: warning: control reaches end of non-void function [-Wreturn-type]
   44 |     });
      |     ^
plahte.cpp: In lambda function:
plahte.cpp:103:5: warning: control reaches end of non-void function [-Wreturn-type]
  103 |     });
      |     ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6036 KB Output is correct
2 Correct 131 ms 5560 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 10596 KB Output is correct
2 Correct 150 ms 8296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 19412 KB Output is correct
2 Correct 270 ms 11876 KB Output is correct
3 Correct 1 ms 296 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 32320 KB Output is correct
2 Correct 483 ms 19216 KB Output is correct
3 Correct 1 ms 304 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 29296 KB Output is correct
2 Correct 496 ms 19404 KB Output is correct
3 Correct 1 ms 212 KB Output is correct