Submission #548966

#	Time	Username	Problem	Language	Result	Execution time	Memory
548966		LucaDantas	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	3 ms	4948 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5+10;

struct Itv {
	int l, r, qtd; // subtasks 1-4 qtd == 1 so I can ignore it for what I'm going to code
} itv[maxn];

int a[maxn]; // quantos caras precisam passar por cada pos

vector<int> opa[maxn];

bool check(int qtd_mov, int M, int sz) {
	vector<int> mov(sz+1);
	for(int i = 1; i <= sz; i++)
		mov[i] = (a[i] + qtd_mov - M + 1) / 2;

	priority_queue<int> q;
	vector<int> add_lazy(sz+1);

	int usados = 0, lazy = 0;
	for(int i = 1; i <= sz; i++) {
		for(int x : opa[i])
			q.push(x);
		
		lazy += add_lazy[i];
		mov[i] += lazy;

		while(mov[i]) {
			if(!q.size() || q.top() <= i) return 0; // não da pra fazer
			--mov[i];
			--lazy;
			add_lazy[q.top()]++;
			q.pop();
			usados++;
		}
	}
	return usados == qtd_mov;
}

int main() {
	int sz, n; scanf("%d %d", &sz, &n);
	for(int i = 0; i < n; i++) {
		scanf("%d %d %d", &itv[i].l, &itv[i].r, &itv[i].qtd);
		if(itv[i].l > itv[i].r) swap(itv[i].l, itv[i].r);
		a[itv[i].l]++, a[itv[i].r]--;
		opa[itv[i].l].push_back(itv[i].r);
	}

	int mx = 0;
	for(int i = 1; i <= sz; i++)
		a[i] += a[i-1], mx = max(mx, a[i]);
	
	int L = 0, R = mx, ans = -1;
	while(L <= R) {
		int M = (L+R) >> 1;
		int qtd_mov = mx - M;
		// a[i] + qtd_mov - 2*mov[i] <= M
		// 2*mov[i] >= a[i] + qtd_mov - M
		// mov[i] >= ceiling( (a[i] + qtd_mov - M) / 2 )
		// mov[i] >= (a[i] + qtd_mov - M + 1) / 2
		if(check(qtd_mov, M, sz))
			ans = M, R = M-1;
		else
			L = M+1;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  int sz, n; scanf("%d %d", &sz, &n);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d %d %d", &itv[i].l, &itv[i].r, &itv[i].qtd);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15