Submission #249804

#	Time	Username	Problem	Language	Result	Execution time	Memory
249804		patrikpavic2	New Home (APIO18_new_home)	C++17	0 / 100	1709 ms	97612 KiB

new_home

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int N = 3e5 + 500;
const int OFF = (1 << 20);
const int KRJ = 1e8;

int zadL[N], zadR[N];
int x[N], ty[N], a[N], b[N], lst_op[N];
int kd[N], gdje[N], n, q, k;
set < pii > S[N];
vector < int > saz;
vector < pair < pii, pii > > s_l, s_r;
vector < int > red;

bool cmp(int A, int B){
	return kd[A] < kd[B];
}

bool fl = 0; int NULA = -KRJ;
int tour[2 * OFF], ans[N], neee[OFF];

void sazmi(){
	for(int i = 0;i < q;i++)
		saz.PB(kd[i]);
	for(int i = 1;i <= n;i++)		
		saz.PB(a[i]), saz.PB(b[i]);
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < q;i++)
		kd[i] = lower_bound(saz.begin(), saz.end(), kd[i]) - saz.begin();
	for(int i = 1;i <= n;i++){
		a[i] = lower_bound(saz.begin(), saz.end(), a[i]) - saz.begin();
		b[i] = lower_bound(saz.begin(), saz.end(), b[i]) - saz.begin();
	}
}

void pocisti(){
	for(int i = 0;i < 2 * OFF;i++)
		tour[i] = NULA;
}

int mrg(int A,int B){
	if(!fl)
		return max(A, B);
	return min(A, B);
}

void update(int i, int a, int b, int lo, int hi, int x){
	if(lo <= a && b <= hi){
		tour[i] = mrg(tour[i], x);
		return;
	}
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi, x);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}

int query(int i){
	int ret = NULA;
	for(i = i + OFF; i ; i /= 2)
		ret = mrg(ret, tour[i]);
	return ret;
}

void dodaj_brid(int l, int r,int trn, int tip){
	//printf("dodajem brid između %d i %d u %d tipa %d\n", l, r, trn, tip);
	if(l == 0 && r == n + 1){
		neee[lst_op[tip]]++;
		neee[trn]--;
		//printf("zabrana od %d do %d\n", lst_op[tip], trn);
	}
	else if(l == 0){
		s_l.PB({{0, x[r]}, {zadL[r], trn - 1}});
		//printf("brid s_l u kor %d dodajem kor %d na interval %d %d\n", 0, x[r], zadL[r], trn - 1);
		zadL[r] = trn;
	}
	else if(r == n + 1){
		s_r.PB({{KRJ, x[l]}, {zadR[l], trn - 1}});
		//printf("brid s_r u kor %d dodajem kor %d na interval %d %d\n", KRJ, x[l], zadR[l], trn - 1);
		zadR[l] = trn;
	}
	else{
		s_l.PB({{(x[l] + x[r] + 1) / 2, x[r]}, {zadL[r], trn - 1}});
		s_r.PB({{(x[l] + x[r]) / 2, x[l]}, {zadR[l], trn - 1}});
		//printf("brid s_l u kor %d dodajem kor %d na interval %d %d\n", (x[l] + x[r] + 1) / 2, x[r], zadL[r], trn - 1);
		//printf("brid s_r u kor %d dodajem kor %d na interval %d %d\n", (x[l] + x[r]) / 2, x[l], zadR[l], trn - 1);
		zadR[l] = trn, zadL[r] = trn;
	}
}

void ubaci(int i, int trn){
	int l = 0, r = n + 1;
	if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].begin())
		l = (--S[ty[i]].lower_bound({x[i], i})) -> Y;
	if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].end())
		r = S[ty[i]].lower_bound({x[i],i}) -> Y;
	dodaj_brid(l, r, trn, ty[i]);
	S[ty[i]].insert({x[i], i});
}

void izbaci(int i, int trn){
	S[ty[i]].erase({x[i], i});
	lst_op[ty[i]] = trn;
	int l = 0, r = n + 1;
	if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].begin())
		l = (--S[ty[i]].lower_bound({x[i], i})) -> Y;
	if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].end())
		r = S[ty[i]].lower_bound({x[i], i}) -> Y;
	dodaj_brid(l, i, trn, ty[i]);
	dodaj_brid(i, r, trn, ty[i]);
}

void gradi_bridove(){
	vector < pii > kda;
	for(int i = 1;i <= n;i++){
		kda.PB({a[i], i});
		kda.PB({b[i] + 1, -i});
	}
	sort(kda.begin(), kda.end());
	for(pii cur : kda){
		if(cur.Y > 0)
			ubaci(cur.Y, cur.X);
		else
			izbaci(-cur.Y, cur.X);
	}
	for(int i = 1;i <= k;i++)
		neee[lst_op[i]]++;
	for(int i = 1;i < OFF;i++)
		neee[i] += neee[i - 1];
}

void racunaj(){
	for(int i = 0;i < q;i++)
		red.PB(i);
	sort(red.begin(), red.end(), cmp);
	sort(s_l.begin(), s_l.end());
	sort(s_r.begin(), s_r.end());
	int j = 0;
	pocisti();
	for(int i = 0;i < q;i++){
		int x = red[i];
		while(j < (int)s_l.size() && s_l[j].X.X <= gdje[x]){
			update(1, 0, OFF - 1, s_l[j].Y.X, s_l[j].Y.Y, s_l[j].X.Y);
			j++;
		}
		ans[x] = max(ans[x], query(kd[x]) - gdje[x]);
	}
	fl = 1; NULA = 2 * KRJ;
	pocisti();
	reverse(red.begin(), red.end());
	j = 0;
	for(int i = 0;i < q;i++){
		int x = red[i];
		while(j < (int)s_r.size() && s_r[j].X.X >= gdje[x]){
			update(1, 0, OFF - 1, s_r[j].Y.X, s_r[j].Y.Y, s_r[j].X.Y);
			j++;
		}
		ans[x] = max(ans[x], gdje[x] - query(kd[x]));
	}	
}

int main(){
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1;i <= n;i++)
		scanf("%d%d%d%d", x + i, ty + i, a + i, b + i);
	for(int i = 0;i < q;i++)
		scanf("%d%d", gdje + i, kd + i);
	sazmi();
	//for(int i = 1;i <= n;i++)
	//	printf("ducan[ %d ] traje od %d do %d na poz %d\n", ty[i], a[i], b[i], x[i]);
	//for(int i = 0;i < q;i++)
	//	printf("hm? mogao bi izgraditi kucu %d godine gospodnje na poz %d\n", kd[i], gdje[i]);
	gradi_bridove();
	racunaj();
	for(int i = 0;i < q;i++){
		if(neee[kd[i]])
			printf("-1\n");
		else
			printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:175: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:177: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, ty + i, a + i, b + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", gdje + i, kd + 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