oj.uz

Submission #51994

# Submission time Handle Problem Language Result Execution time Memory
51994 2018-06-22T22:45:10 Z pzdba New Home (APIO18_new_home) C++14
0 / 100
 3370 ms 114204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 55 ms 47540 KB Output is correct
4 Incorrect 53 ms 47608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 55 ms 47540 KB Output is correct
4 Incorrect 53 ms 47608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2078 ms 90592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3370 ms 114204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 55 ms 47540 KB Output is correct
4 Incorrect 53 ms 47608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 55 ms 47540 KB Output is correct
4 Incorrect 53 ms 47608 KB Output isn't correct
5 Halted 0 ms 0 KB -