Submission #296252

#	Time	Username	Problem	Language	Result	Execution time	Memory
296252		patrikpavic2	Pinball (JOI14_pinball)	C++17	100 / 100	268 ms	23916 KiB

pinball

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

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

using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;

const int N = 3e5 + 500;
const ll INF = 1e15;
const int OFF = (1 << 19);

int m, n, L[N], R[N], C[N], Q[N];
vector < int > saz;
pll T[2 * OFF], NULA = {INF, INF};

pll mrg(pll A, pll B){
	return {min(A.X, B.X), min(A.Y, B.Y)};
}

void update(int i, pll nw){
	T[OFF + i] = mrg(T[OFF + i], nw);
	for(i = (i + OFF) / 2 ; i ; i /= 2)
		T[i] = mrg(T[2 * i], T[2 * i + 1]);
}

pll query(int i, int a, int b, int lo, int hi){
	if(lo <= a && b <= hi)
		return T[i];
	if(a > hi || b < lo)
		return NULA;
	return mrg(query(2 * i, a, (a + b) / 2,lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int main(){
	for(int i = 0;i < 2 * OFF;i++)
		T[i] = NULA;
	scanf("%d%d", &m, &n);
	saz.PB(1); saz.PB(n);
	for(int i = 0;i < m;i++){
		scanf("%d%d%d%d", L + i, R + i, Q + i, C + i);
		saz.PB(L[i]); saz.PB(R[i]); saz.PB(Q[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	n = (int)saz.size() - 1;
	update(0, {0, INF}); update(n, {INF, 0});
	for(int i = 0;i < m;i++){
		L[i] = lower_bound(saz.begin(), saz.end(), L[i]) - saz.begin();
		R[i] = lower_bound(saz.begin(), saz.end(), R[i]) - saz.begin();
		Q[i] = lower_bound(saz.begin(), saz.end(), Q[i]) - saz.begin();
	}
	ll sol = INF;
	for(int i = 0;i < m;i++){
		pll ja = query(1, 0, OFF - 1, L[i], R[i]);
		sol = min(sol, ja.X + ja.Y + C[i]);
		ja.X += C[i], ja.Y += C[i];
		//printf("%lld %lld\n", ja.X, ja.Y);
		update(Q[i], ja);
	}
	if(sol == INF)
		printf("-1\n");
	else
		printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d", &m, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d%d%d%d", L + i, R + i, Q + i, C + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49