oj.uz

답안 #625239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625239 2022-08-09T16:50:19 Z QwertyPi 새 집 (APIO18_new_home) C++14
0 / 100
 4851 ms 623076 KB 
#include <bits/stdc++.h>
#pragma optimize("unroll-loops")
#pragma optimize("Ofast")
const int N = 300013;
using namespace std;

struct Store{
	int x, ty, a, b;
};

struct Query{
	int t, ty, x, id;
};

struct Pair{
	Pair() = default;
	Pair(int _x, int _y, int _d) : x(_x), y(_y), d(_d){};
	int x, y, d;
};

struct DS{
	vector<int> sp[N * 2], bits[N * 2];
	string name;
	DS() = default;
	DS(string _n) : name(_n){}
	void insert(Pair p){
		int x = p.x + 1, y = p.y + 1;
		for(int i = x; i < N * 2; i += i & -i){
			sp[i].push_back(y);
		}
	}
	void parse(){
		for(int i = 0; i < N * 2; i++) sp[i].push_back(0);
		for(int i = 0; i < N * 2; i++){
			sort(sp[i].begin(), sp[i].end());
			sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
			bits[i].resize(sp[i].size());
		}
	}
	void add(Pair p){
		int x = p.x + 1, y = p.y + 1;
		for(int i = x; i < N * 2; i += i & -i){
			int idx = lower_bound(sp[i].begin(), sp[i].end(), y) - sp[i].begin();
			for(int j = idx; j < sp[i].size(); j += j & -j){
				bits[i][j] += p.d;
			}
		}
	}
	int qry(int x, int y){
		x++; y++;
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			int idx = upper_bound(sp[i].begin(), sp[i].end(), y) - 1 - sp[i].begin();
			for(int j = idx; j; j -= j & -j){
				ret += bits[i][j];
			}
		}
		return ret;
	}
	int qry(int x1, int x2, int y1, int y2){
		return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
	}
} ds;

struct BIT{
	int bit[N];
	void add(int p, int v){
		p++;
		for(int i = p; i < N; i += i & -i){
			bit[i] += v;
		}
	}
	int qry(int p){
		int ret = 0;
		p++;
		for(int i = p; i; i -= i & -i){
			ret += bit[i];
		}
		return ret;
	}
	int qry(int l, int r){
		return qry(r) - qry(l - 1);
	}
} bit;

vector<Store> stores;
vector<Query> Q;
vector<Pair> C[N * 3], D[N * 3];
int m;
int p[N * 2];
int ans[N];

int n, k, q;

bool check(int x1, int x2){
	int l = lower_bound(p, p + m, x1) - p;
	int r = upper_bound(p, p + m, x2) - 1 - p;
	int c1 = bit.qry(l, r);
	int c2 = ds.qry(l, r, l, r);
	assert(c1 - c2 >= 0 && c1 - c2 <= k);
	return c1 - c2 == k;
}

int qry(int x){
	int l = 0, r = 1e9;
	while(l != r){
		int mid = (l + r) / 2;
		if(check(p[x] - mid, p[x] + mid)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	return l >= 9e8 ? -1 : l;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	vector<int> sp;
	for(int i = 0; i < n; i++){
		int x, ty, a, b;
		cin >> x >> ty >> a >> b;
		stores.push_back({x, ty, a, b + 1}); 
	}
	for(int i = 0; i < q; i++){
		int x, t;
		cin >> x >> t;
		Q.push_back({t, 2, x, i});
	}
	{
		vector<int> xs;
		for(auto st : stores){
			xs.push_back(st.x);
		}
		for(auto q : Q){
			xs.push_back(q.x);
		}
		sort(xs.begin(), xs.end());
		xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
		m = xs.size();
		for(int i = 0; i < m; i++){
			p[i] = xs[i];
		}
		map<int, int> M;
		for(int i = 0; i < m; i++){
			M[xs[i]] = i;
		}
		for(auto& st : stores){
			st.x = M[st.x];
		}
		for(auto& q : Q){
			q.x = M[q.x];
		}
	}
	for(auto st : stores){
		Q.push_back({st.a, 1, st.x, st.ty});
		Q.push_back({st.b + 1, 0, st.x, st.ty});
	}
	
	sort(Q.begin(), Q.end(), [](Query a, Query b){
		return a.t < b.t || a.t == b.t && a.ty < b.ty;
	});
	multiset<int> vset[N];
	for(int i = 0; i < Q.size(); i++){
		Query q = Q[i];
		auto ptr = vset[q.id].begin();
		switch(q.ty){
			case 0:
				ptr = vset[q.id].lower_bound(q.x);
				assert(ptr != vset[q.id].end());
				if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
				if(next(ptr) != vset[q.id].end()) C[i].push_back({*ptr, *next(ptr), -1});
				if(ptr != vset[q.id].begin() && next(ptr) != vset[q.id].end()) C[i].push_back({*prev(ptr), *next(ptr), 1});
				D[i].push_back({q.x, -1, -1});
				vset[q.id].erase(ptr);
				break;
			case 1:
				ptr = vset[q.id].lower_bound(q.x);
				if(ptr != vset[q.id].end() && ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
				if(ptr != vset[q.id].end()) C[i].push_back({q.x, *ptr, 1});
				if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), q.x, 1});
				D[i].push_back({q.x, -1, 1});
				vset[q.id].insert(q.x);
				break;
			case 2:
				break;
			default:
				assert(false);
		}
	}
	for(int i = 0; i < Q.size(); i++){
		for(auto p : C[i]){
			ds.insert(p);
		}
	}
	ds.parse();
	for(int i = 0; i < Q.size(); i++){
		for(auto p : C[i]){
			ds.add(p);
		}
		for(auto p : D[i]){
			bit.add(p.x, p.d);
		}
		Query q = Q[i];
		switch(q.ty){
			case 0:
				break;
			case 1:
				break;
			case 2: ans[q.id] = qry(q.x); break;
			default: assert(false);
		}
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << '\n';
	}
}

Compilation message

new_home.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("unroll-loops")
      | 
new_home.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
new_home.cpp: In member function 'void DS::add(Pair)':
new_home.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int j = idx; j < sp[i].size(); j += j & -j){
      |                     ~~^~~~~~~~~~~~~~
new_home.cpp: In lambda function:
new_home.cpp:163:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  163 |   return a.t < b.t || a.t == b.t && a.ty < b.ty;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~
new_home.cpp:193:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~
new_home.cpp:199:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 122416 KB Output is correct
2 Correct 100 ms 122396 KB Output is correct
3 Correct 99 ms 122408 KB Output is correct
4 Correct 100 ms 122436 KB Output is correct
5 Incorrect 114 ms 122848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 122416 KB Output is correct
2 Correct 100 ms 122396 KB Output is correct
3 Correct 99 ms 122408 KB Output is correct
4 Correct 100 ms 122436 KB Output is correct
5 Incorrect 114 ms 122848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3139 ms 501860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4851 ms 623076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 122416 KB Output is correct
2 Correct 100 ms 122396 KB Output is correct
3 Correct 99 ms 122408 KB Output is correct
4 Correct 100 ms 122436 KB Output is correct
5 Incorrect 114 ms 122848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 122416 KB Output is correct
2 Correct 100 ms 122396 KB Output is correct
3 Correct 99 ms 122408 KB Output is correct
4 Correct 100 ms 122436 KB Output is correct
5 Incorrect 114 ms 122848 KB Output isn't correct
6 Halted 0 ms 0 KB -