제출 #548975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548975		LucaDantas	Arranging Tickets (JOI17_arranging_tickets)	C++17	85 / 100	277 ms	13752 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] > 0) {
			if(!q.size() || q.top() <= i) return 0; // não da pra fazer
			--mov[i];
			--lazy;
			add_lazy[q.top()]++;
			q.pop();
			usados++;
		}
	}
	// printf("%d %d\n", usados, qtd_mov);
	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) || check(qtd_mov+1, M, sz))
			ans = M, R = M-1;
		else
			L = M+1;

		// printf("%d\n", M);
	}
	printf("%d\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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