oj.uz

답안 #135494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135494 2019-07-24T06:49:27 Z 이온조(#3249) MP3 Player (CEOI10_mp3player) C++14
40 / 100
 1000 ms 1776 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second

struct seg {
	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]);
	}
	pii get(int idx, int s, int e) {
		upl(idx, s, e);
		return {mn[idx], mx[idx]};
	}
	seg(int N, int V2) {
		mn.resize(4*N);
		mx.resize(4*N);
		L.resize(4*N);
		init(1, 1, N, V2);
	}
};

int C[100009];
char T[100009];
vector<pii> S;
bool chk[100009];

int main() {
	int N, VM, V2; scanf("%d%d%d",&N,&VM,&V2);
	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});
	for(int k=0; k<N-1; k++) {
		int cost = S[k].X;
		chk[S[k].Y] = 1;
		while(cost == S[k+1].X) {
			++k;
			chk[S[k].Y] = 1;
		}

		bool f = 1;
		int L = V2, R = V2;
		for(int i=N; i>=1; i--) {
			if(!chk[i]) continue;
			if(T[i] == '+') {
				if(R == VM) --L;
				else --L, --R;
				L = max(L, 0);
			}
			if(T[i] == '-') {
				if(L == 0) ++R;
				else ++L, ++R;
				R = min(R, VM);
			}
			if(R < L) f = 0;
		}
		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 seg::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 seg::upd(int, int, int, int, int, int)':
mp3player.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
mp3player.cpp: In function 'int main()':
mp3player.cpp:62:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, VM, V2; scanf("%d%d%d",&N,&VM,&V2);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:65: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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 376 KB Output is correct
2 Correct 30 ms 504 KB Output is correct
3 Correct 26 ms 504 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 1140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 1776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 1776 KB Time limit exceeded
2 Halted 0 ms 0 KB -