oj.uz

Submission #135548

# Submission time Handle Problem Language Result Execution time Memory
135548 2019-07-24T08:05:28 Z 이온조(#3249) MP3 Player (CEOI10_mp3player) C++14
90 / 100
 110 ms 7944 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second

const int INF = 1e9;

struct segtree {
	vector<int> mn, mx, L;
	void init(int idx, int s, int e, int 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, int 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, int 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, int 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;
	}
	int 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));
	}
	int 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, int V2) {
		mn.resize(4*N);
		mx.resize(4*N);
		L.resize(4*N);
		init(1, 1, N, V2);
	}
};

int N, 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, i, -1);
	if(T[i] == '-') seg.upd(1, 1, N, 1, i, +1);
}

int main() {
	int VM, V2; scanf("%d%d%d",&N,&VM,&V2);
	for(int i=1; i<=N; i++) {
		scanf(" %c%d", &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});
	int ans = S[0].X - 1, V1 = V2;
	segtree seg(N, V2);
	for(int k=0; k<N-1; k++) {
		int cost = S[k].X;
		add(seg, S[k].Y);
		while(cost == S[k+1].X) {
			++k;
			add(seg, S[k].Y);
		}
		bool f = 1; int R;
		int fu = seg.findU(1, 1, N, VM);
		int fd = seg.findD(1, 1, N, 0);

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

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

Compilation message

mp3player.cpp: In member function 'void segtree::init(int, int, int, 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, 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, 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, int)':
mp3player.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In member function '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 '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:97: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:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d", &T[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2036 KB Output is correct
2 Correct 21 ms 2036 KB Output is correct
3 Correct 18 ms 2008 KB Output is correct
4 Correct 19 ms 2036 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2292 KB Output is correct
2 Correct 20 ms 2212 KB Output is correct
3 Correct 21 ms 2308 KB Output is correct
4 Correct 29 ms 2148 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2672 KB Output is correct
2 Incorrect 33 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3696 KB Output is correct
2 Correct 36 ms 3696 KB Output is correct
3 Correct 38 ms 3568 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7656 KB Output is correct
2 Correct 80 ms 7944 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 7788 KB Output is correct
2 Correct 83 ms 7760 KB Output is correct