Submission #135676

#	Time	Username	Problem	Language	Result	Execution time	Memory
135676		onjo0127	MP3 Player (CEOI10_mp3player)	C++11	100 / 100	121 ms	13712 KiB

mp3player

#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
#define X first
#define Y second

const long long INF = 1LL * 1e18;

struct segtree {
	vector<long long> mn, mx, L;
	void init(int idx, int s, int e, long long v) {
		mn[idx] = mx[idx] = v;
		if(s == e) return;
		int m = s+e >> 1;
		init(idx*2, s, m, v);
		init(idx*2+1, m+1, e, v);
	}
	void upl(int idx, int s, int e) {
		if(L[idx]) {
			mn[idx] += L[idx];
			mx[idx] += L[idx];
			if(s != e) {
				L[idx*2] += L[idx];
				L[idx*2+1] += L[idx];
			}
			L[idx] = 0;
		}
	}
	void upd(int idx, int s, int e, int l, int r, long long v) {
		upl(idx, s, e);
		if(r < s || e < l) return;
		if(l <= s && e <= r) {
			L[idx] += v;
			upl(idx, s, e);
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, l, r, v);
		upd(idx*2+1, m+1, e, l, r, v);
		mn[idx] = min(mn[idx*2], mn[idx*2+1]);
		mx[idx] = max(mx[idx*2], mx[idx*2+1]);
	}
	int findU(int idx, int s, int e, long long v) {
		upl(idx, s, e);
		if(mx[idx] < v) return 0;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = findU(idx*2+1, m+1, e, v);
		if(tmp == 0) return findU(idx*2, s, m, v);
		return tmp;
	}
	int findD(int idx, int s, int e, long long v) {
		upl(idx, s, e);
		if(mn[idx] > v) return 0;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = findD(idx*2+1, m+1, e, v);
		if(tmp == 0) return findD(idx*2, s, m, v);
		return tmp;
	}
	long long gmn(int idx, int s, int e, int l, int r) {
		assert(l <= r);
		upl(idx, s, e);
		if(r < s || e < l) return INF;
		if(l <= s && e <= r) return mn[idx];
		int m = s+e >> 1;
		return min(gmn(idx*2, s, m, l, r), gmn(idx*2+1, m+1, e, l, r));
	}
	long long gmx(int idx, int s, int e, int l, int r) {
		assert(l <= r);
		upl(idx, s, e);
		if(r < s || e < l) return -INF;
		if(l <= s && e <= r) return mx[idx];
		int m = s+e >> 1;
		return max(gmx(idx*2, s, m, l, r), gmx(idx*2+1, m+1, e, l, r));
	}
	segtree(int N, long long V2) {
		mn.resize(4*N);
		mx.resize(4*N);
		L.resize(4*N);
		init(1, 1, N, V2);
	}
};

int N;
long long C[200009];
char T[200009];
vector<pii> S;
bool chk[200009];

void add(segtree &seg, int i) {
	chk[i] = 1;
	if(T[i] == '+') seg.upd(1, 1, N+1, 1, i, -1);
	if(T[i] == '-') seg.upd(1, 1, N+1, 1, i, +1);
}

int main() {
	int VM, V2; scanf("%d%d%d",&N,&VM,&V2);
	for(int i=1; i<=N; i++) {
		scanf(" %c %lld", &T[i], &C[i]);
		if(i >= 2) S.push_back({C[i] - C[i-1], i});
	}
	sort(S.begin(), S.end());
	S.push_back({-1, -1});
	long long ans = S[0].X - 1, V1 = V2;
	segtree seg(N+1, V2);
	for(int k=0; k<N-1; k++) {
		long long cost = S[k].X;
		add(seg, S[k].Y);
		while(cost == S[k+1].X) {
			++k;
			add(seg, S[k].Y);
		}
		bool f = 1; long long R = -1;
		int fu = seg.findU(1, 1, N+1, VM);
		int fd = seg.findD(1, 1, N+1, 0);

		if(fu == 0 && fd == 0) R = seg.gmx(1, 1, N+1, 1, 1);
		else {
			assert(fd != fu);
			if(fd > fu) {
				if(seg.gmn(1, 1, N+1, fu+1, fd) < 0) f = 0;
				else {
					if(fu == 0) R = seg.gmx(1, 1, N+1, 1, 1);
					else R = VM;
				}
			}
			else {
				if(seg.gmx(1, 1, N+1, fd+1, fu) > VM) f = 0;
				else R = VM;
			}
		}

		if(f) {
			if(k+2 == N) return !printf("infinity");
			assert(R != -1);
			ans = S[k+1].X - 1; V1 = R;
		}
	}
	assert(ans >= 0);
	printf("%lld %lld", ans, V1);
	return 0;
}

Compilation message (stderr)

mp3player.cpp: In member function 'void segtree::init(int, int, int, long long int)':
mp3player.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function 'void segtree::upd(int, int, int, int, int, long long int)':
mp3player.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function 'int segtree::findU(int, int, int, long long int)':
mp3player.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function 'int segtree::findD(int, int, int, long long int)':
mp3player.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function 'long long int segtree::gmn(int, int, int, int, int)':
mp3player.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function 'long long int segtree::gmx(int, int, int, int, int)':
mp3player.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In function 'int main()':
mp3player.cpp:98:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int VM, V2; scanf("%d%d%d",&N,&VM,&V2);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %lld", &T[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10