Submission #112049

#	Time	Username	Problem	Language	Result	Execution time	Memory
112049		ecasdqina	New Home (APIO18_new_home)	C++14	12 / 100	2969 ms	26380 KiB

new_home

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

using namespace std;
template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree
{
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
  using P = function< OperatorMonoid(OperatorMonoid, int) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const P p;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F f, const G g, const H h, const P p,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), p(p), M1(M1), OM0(OM0)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x)
  {
    data[k + sz] = x;
  }

  void build()
  {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int len)
  {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], p(lazy[k], len));
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r)
  {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, r - l);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x)
  {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r)
  {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b)
  {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k)
  {
    return query(k, k + 1);
  }
};

int main() {
	int n, q, K; scanf("%d%d%d", &n, &K, &q);
	std::vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
	for(int i = 0; i < n; i++) {
		scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]); t[i]--;
	}
	for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
	
	std::function<int (std::set<std::pair<int, int>>&, int)> calcDist = [](std::set<std::pair<int, int>>& st, int t) {
		auto it = st.lower_bound(std::make_pair(t, -1));
		if(it == st.end()) it = std::prev(it);
		if(it == st.begin()) return std::abs((*it).first - t);
		return std::min(std::abs((*it).first - t),
						 std::abs((*std::prev(it)).first - t));
	};
	
	std::vector<int> ans(q, -1);
	if(n <= 400 and q <= 400) {
		for(int i = 0; i < q; i++) {
			std::vector<int> vec(K, 1 << 30);
			for(int j = 0; j < n; j++) {
				if(!(a[j] <= y[i] and y[i] <= b[j])) continue;
				vec[t[j]] = std::min(vec[t[j]], std::abs(x[j] - l[i]));
			}
			
			
			for(int j = 0; j < K; j++) {
				if(vec[j] == 1 << 30) {
					ans[i] = -1;
					break;
				}
				ans[i] = std::max(ans[i], vec[j]);
			}
		}
	} else if(K <= 400) {
		std::vector<std::pair<int, int>> A, B;
		for(int i = 0; i < n; i++) {
			A.push_back({a[i], i});
			B.push_back({b[i] + 1, i});
		}
		sort(begin(A), end(A)); sort(begin(B), end(B));
		
		std::vector<std::pair<int, int>> query;
		for(int i = 0; i < q; i++) query.push_back({y[i], i});
		sort(begin(query), end(query));
		
		int curA = 0, curB = 0;
		std::vector<std::set<std::pair<int, int>>> vec(K);
		for(auto YYS: query) {
			int L = l[YYS.second], Y = y[YYS.second];
			while(curA < A.size() and A[curA].first <= Y) {
				int p = A[curA++].second;
				vec[t[p]].insert({x[p], p});
			}
			while(curB < B.size() and B[curB].first <= Y) {
				int p = B[curB++].second;
				vec[t[p]].erase({x[p], p});
			}
			
			int ret = 0;
			for(int k = 0; k < K; k++) {
				if(vec[k].empty()) {
					ret = -1;
					break;
				}
				
				ret = std::max(ret, calcDist(vec[k], L));
			}
			ans[YYS.second] = ret;
		}
	} else {
		for(int i = 0; i < n; i++) assert(a[i] == 1 and b[i] == 1e8);
		
		std::vector<std::pair<int, std::pair<int, int>>> A;
		std::vector<std::vector<int>> vec(K);
		for(int i = 0; i < n; i++) {
			vec[t[i]].push_back(x[i]);
			A.push_back({x[i], {t[i], 1}});
		}
		for(int k = 0; k < K; k++) {
			if(vec[k].empty()) {
				while(K--) printf("-1\n");
				return 0;
			}
			sort(begin(vec[k]), end(vec[k]));
			A.push_back({(vec[k][0] + 1) >> 1, {k, 0}});
			for(int i = 0; i < vec[k].size() - 1; i++) {
				A.push_back({(vec[k][i] + vec[k][i + 1] + 1) >> 1, {k, 0}});
			}
		}
		sort(begin(A), end(A));
		
		std::vector<std::pair<int, int>> query(1, {0, 0});
		for(int i = 0; i < q; i++) query.push_back({l[i], i});
		sort(begin(query), end(query));
		
		int cur = 0;
		auto f = [](int a, int b) { return std::max(a, b); };
		auto g = [](int a, int b) { return a + b; };
		auto h = [](int a, int b) { return a + b; };
		auto p = [](int a, int b) { return a; };
		LazySegmentTree<int> X(K, f, g, h, p, 0, 0), Y(K, f, g, h, p, 0, 0);
		for(int i = 0; i < K; i++) Y.set(i, vec[i].front()); Y.build();
		for(int i = 0; i < query.size(); i++) {
			int L = query[i].first;
			if(i) {
				X.update(0, K, query[i].first - query[i - 1].first);
				Y.update(0, K, query[i - 1].first - query[i].first);
			}
			while(cur < A.size() and A[cur].first <= L) {
				int type = A[cur].second.second, p = A[cur].second.first, x = A[cur++].first;
				
				if(type == 1) {
					X.update(p, p + 1, L - x);
					Y.update(p, p + 1, 0);
					vec[p].erase(begin(vec[p]));
				} else if(type == 0) {
					Y.update(p, p + 1, vec[p].front() - L);
					X.update(p, p + 1, 0);
				}
			}
			
			/*
			cout << "X: "; for(int j = 0; j < K; j++) cout << X[j] << " "; cout << endl;
			cout << "Y: "; for(int j = 0; j < K; j++) cout << Y[j] << " "; cout << endl;
			cout << endl;
			*/
			
			if(i) ans[query[i].second] = std::max(X.query(0, K), Y.query(0, K));
		}
	}
	for(auto v: ans) printf("%d\n", v);
	return 0;
}
/*
4 2 4
3 1 1 100000000
9 2 1 100000000
7 2 1 100000000
4 1 1 100000000
5 3
5 6
5 9
1 10
*/

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:165:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curA < A.size() and A[curA].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curB < B.size() and B[curB].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:201:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < vec[k].size() - 1; i++) {
                   ~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:217:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 0; i < K; i++) Y.set(i, vec[i].front()); Y.build();
   ^~~
new_home.cpp:217:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 0; i < K; i++) Y.set(i, vec[i].front()); Y.build();
                                                        ^
new_home.cpp:218:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < query.size(); i++) {
                  ~~^~~~~~~~~~~~~~
new_home.cpp:224:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(cur < A.size() and A[cur].first <= L) {
          ~~~~^~~~~~~~~~
new_home.cpp:116:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q, K; scanf("%d%d%d", &n, &K, &q);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]); t[i]--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:121:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20