Submission #51994

#	Time	Username	Problem	Language	Result	Execution time	Memory
51994		pzdba	New Home (APIO18_new_home)	C++14	0 / 100	3370 ms	114204 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
map<int, int> ht;
map<int, int>::iterator its;
int x[300005], t[300005], a[300005], b[300005];
int l[300005], y[300005];


int tot[300005];
int mn[1000005], mx[1000005];
bool ok[1000005];

vector<int> st[1000005], en[1000005];

int main(){
	int n, k, q;
	scanf("%d%d%d", &n, &k, &q);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
		ht[a[i]] = 1;
		ht[b[i]] = 1;
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d", &l[i], &y[i]);
		ht[y[i]] = 1;
	}
	int sum = 1;
	for(its = ht.begin();its != ht.end();its++){
		its->second = sum++;
	}
	sum--;
	for(int i=1;i<=n;i++){
		a[i] = ht[a[i]];
		b[i] = ht[b[i]];
		st[a[i]].push_back(i);
		en[b[i]].push_back(i);
	}
	int cnt = 0;
	set<pii> ms;
	for(int i=1;i<=sum;i++){
		for(int j=0;j<st[i].size();j++){
			int idx = st[i][j];
			tot[t[idx]]++;
			if(tot[t[idx]] == 1) cnt++;
			ms.insert(pii(x[idx], idx));
		}
		if(cnt == k){
			ok[i] = 1;
			mn[i] = ms.begin()->first;
			mx[i] = (--ms.end())->first;
		}
		for(int j=0;j<en[i].size();j++){
			int idx = en[i][j];
			tot[t[idx]]--;
			if(tot[t[idx]] == 0) cnt--;
			ms.erase(ms.find(pii(x[idx], idx)));
		}
	}
	for(int i=1;i<=q;i++){
		y[i] = ht[y[i]];
		if(!ok[y[i]]) printf("%d\n", -1);
		else printf("%d\n", max(abs(mn[y[i]]-l[i]), abs(mx[y[i]]-l[i])));
	}
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<st[i].size();j++){
               ~^~~~~~~~~~~~~
new_home.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<en[i].size();j++){
               ~^~~~~~~~~~~~~
new_home.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:20: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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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