oj.uz

Submission #135505

# Submission time Handle Problem Language Result Execution time Memory
135505 2019-07-24T07:13:50 Z 이온조(#3249) MP3 Player (CEOI10_mp3player) C++14
90 / 100
 111 ms 7820 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) {
		if(s == e) {
			mn[idx] = mx[idx] = v;
			return;
		}
		int m = s+e >> 1;
		init(idx*2, s, m, v);
		init(idx*2+1, m+1, e, v);
		mn[idx] = mx[idx] = 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 -1;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = findU(idx*2+1, m+1, e, v);
		if(tmp == -1) 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 -1;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = findD(idx*2+1, m+1, e, v);
		if(tmp == -1) return findD(idx*2, s, m, v);
		return tmp;
	}
	int gmn(int idx, int s, int e, int l, int 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) {
		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[100009];
char T[100009];
vector<pii> S;
bool chk[100009];

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);
}

void show(segtree &seg) {
	puts("SHOW");
	for(int i=1; i<=N; i++) {
		if(chk[i]) printf("%c %d, sum: %d\n", T[i], C[i], seg.gmx(1, 1, N, i, i));
	}
	puts("----------------");
}

int main() {
	int VM, V2; scanf("%d%d%d",&N,&VM,&V2);
	if(VM == 0) return !printf("infinity");
	int ans = 0, V1 = 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});

	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 == -1 && fd == -1) R = seg.gmx(1, 1, N, 1, 1);
		else if(fd > fu) {
			if(seg.gmn(1, 1, N, fu+1, fd) < 0) f = 0;
			else {
				if(fu == -1) 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\n", ans, V1);
	return 0;
}

Compilation message

mp3player.cpp: In member function 'void segtree::init(int, int, int, int)':
mp3player.cpp:16: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:40: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:50: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:59: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:68: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:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In function 'int main()':
mp3player.cpp:106: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:110: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 548 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 416 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2100 KB Output is correct
2 Correct 21 ms 2036 KB Output is correct
3 Correct 18 ms 2036 KB Output is correct
4 Correct 20 ms 2036 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2356 KB Output is correct
2 Correct 20 ms 2292 KB Output is correct
3 Correct 20 ms 2292 KB Output is correct
4 Correct 29 ms 2036 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2676 KB Output is correct
2 Incorrect 32 ms 2676 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 54 ms 3704 KB Output is correct
2 Correct 37 ms 3792 KB Output is correct
3 Correct 38 ms 3436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7608 KB Output is correct
2 Correct 79 ms 7720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 7760 KB Output is correct
2 Correct 80 ms 7820 KB Output is correct