oj.uz

Submission #854362

# Submission time Handle Problem Language Result Execution time Memory
854362 2023-09-27T05:40:05 Z clonemaasteruwu Plahte (COCI17_plahte) C++17
160 / 160
 159 ms 20764 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//corner case
//emplace >> default constructor

void solve() {
  int n,m;cin >> n >> m;
  vector<tuple<int,int,int,int,int,int>> event;
  event.reserve(n+m);
  vector<int> y_comp;
  y_comp.reserve(2*n+m);
  for(int i=0;i<n;i++) {
	int x1,y1,x2,y2;
	cin >> x1 >> y1 >> x2 >> y2;
	event.emplace_back(x1,y1,x2,y2,0,i);
	y_comp.push_back(y1), y_comp.push_back(y2);
  }
  for(int i=0;i<m;i++){
	int x,y,k;cin >> x >> y >> k;
	event.emplace_back(x,INT_MAX,y,k,1,0);
	y_comp.push_back(y);
  }
  sort(y_comp.begin(), y_comp.end());
  int tn = unique(y_comp.begin(), y_comp.end()) - y_comp.begin();
  y_comp.resize(tn);
  auto get_yid = [&](int y){
	return lower_bound(y_comp.begin(),y_comp.end(),y) - y_comp.begin();
  };
  sort(event.begin(), event.end());
  vector<pair<int,int>> seg(2*tn,{-1,-1});
  int id = 0;
  auto update = [&](int l,int r,int v){
	for(l+=tn,r+=tn;l<r;l>>=1,r>>=1){
	  if(l&1) seg[l++] = {v,id};
	  if(r&1) seg[--r] = {v,id};
	}
	id++;
  };
  auto query = [&](int p){
	p+=tn;
	auto [re,lid] = seg[p];
	while(p>1){
	  p>>=1;
	  if(seg[p].second > lid){
		re = seg[p].first;
		lid = seg[p].second;
	  }
	}
	return re;
  };
  vector<set<int>> track(n);
  vector<int> parent(n,-1);
  vector<int> res(n);
  priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<>> pq;
  auto process_up_to = [&](int x){
	while(!pq.empty()){
	  auto [x2,i,y1,y2] = pq.top();
	  if(x2 >= x)
		break;
	  pq.pop();
	  res[i] = track[i].size();
	  int pi = parent[i];
	  if(pi!=-1){
		if(track[i].size() > track[pi].size()){
		  swap(track[i],track[pi]);
		}
		track[pi].insert(track[i].begin(),track[i].end());
		track[i].clear();
	  }
	  update(y1,y2+1,pi);
	}
  };
  for(auto e:event){
	if(!get<4>(e)){
	  auto [x1,y1,x2,y2,_,i] = e;
	  process_up_to(x1);
	  y1 = get_yid(y1),y2 = get_yid(y2);
	  int pi = query(y1);
	  parent[i] = pi;
	  update(y1,y2+1,i);
	  pq.emplace(x2,i,y1,y2);
	} else {
	  auto [x,_1,y,k,_2,_3] = e;
	  process_up_to(x);
	  y = get_yid(y);
	  int qy = query(y);
	  if(qy!=-1) track[qy].insert(k);
	}
  }
  process_up_to(INT_MAX);
  for(int i:res) cout << i << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
//  int t;
//  cin >> t;
//  for (int i = 1; i <= t; i++)
	solve();
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6496 KB Output is correct
2 Correct 48 ms 6736 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8136 KB Output is correct
2 Correct 54 ms 7712 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13120 KB Output is correct
2 Correct 95 ms 12488 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 20764 KB Output is correct
2 Correct 155 ms 19668 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 20548 KB Output is correct
2 Correct 159 ms 19540 KB Output is correct
3 Correct 1 ms 344 KB Output is correct