oj.uz

Submission #135405

# Submission time Handle Problem Language Result Execution time Memory
135405 2019-07-24T04:56:46 Z 윤교준(#3250) MP3 Player (CEOI10_mp3player) C++14
100 / 100
 69 ms 7812 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MX = 131072;

struct NOD {
	NOD();
	ll d, M, m;
	NOD operator + (const NOD&) const;
	bool f(ll T) { return m+d <= T && T <= M+d; }
};

struct SEG {
	NOD dt[MX*2];

	void init() { for(int i = MX*2; i--;) dt[i] = NOD(); }
	void upd(int, bool);
	NOD get() { return dt[1]; }
} seg;

ll A[MAXN];
int O[MAXN];
bitset<MAXN> B;

ll K, T, Ans = 0, AnsT;
int N;

void SEG::upd(int x, bool r) {
	x += MX;
	if(r) {
		dt[x].d = 1;
		dt[x].M = K-1;
		dt[x].m = 0;
	} else {
		dt[x].d = -1;
		dt[x].M = K;
		dt[x].m = 1;
	}
	for(x >>= 1; x; x >>= 1)
		dt[x] = dt[x<<1] + dt[x<<1|1];
}

NOD :: NOD() : d(0), M(K), m(0) {}
NOD NOD::operator + (const NOD &r) const {
	NOD ret;
	if(M + d <= r.m) {
		ret.M = ret.m = K;
		ret.d = r.m + r.d - K;
		return ret;
	}
	if(m + d >= r.M) {
		ret.M = ret.m = K;
		ret.d = r.M + r.d - K;
		return ret;
	}

	ret.d = d + r.d;
	if(M + d >= r.M) ret.M = r.M - d;
	else ret.M = M;
	if(m + d <= r.m) ret.m = r.m - d;
	else ret.m = m;

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K >> T;
	for(int i = 0; i < N; i++) {
		char c;
		cin >> c >> A[i];
		B[i] = '+' == c;
	}
	iota(O, O+N, 0); sort(O+1, O+N, [&](int a, int b) {
		return A[a]-A[a-1] < A[b]-A[b-1];
	});

	seg.init(); AnsT = T;
	for(int s = 1, e; s < N; s = e) {
		ll t = A[O[s]] - A[O[s]-1];
		for(e = s+1; e < N && A[O[e]] - A[O[e]-1] == t; e++);
		for(int oi = s, i; oi < e; oi++) {
			i = O[oi];
			seg.upd(i, B[i]);
		}
		NOD ret = seg.get();
		if(ret.f(T)) {
			Ans = t;
			AnsT = T-ret.d;
			if(ret.M + ret.d == T)
				AnsT = K;
		}
	}

	{
		ll mn = INFLL + 1;
		for(int i = 1; i < N; i++) {
			ll t = A[i]-A[i-1];
			if(Ans < t && t < mn) mn = t;
		}
		Ans = mn-1;
	}
	if(INFLL <= Ans) puts("infinity");
	else cout << Ans << ' ' << AnsT << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6544 KB Output is correct
2 Correct 8 ms 6524 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6568 KB Output is correct
2 Correct 9 ms 6524 KB Output is correct
3 Correct 12 ms 6624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6480 KB Output is correct
2 Correct 9 ms 6492 KB Output is correct
3 Correct 9 ms 6492 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6848 KB Output is correct
2 Correct 25 ms 6884 KB Output is correct
3 Correct 22 ms 6848 KB Output is correct
4 Correct 18 ms 6776 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6904 KB Output is correct
2 Correct 24 ms 6904 KB Output is correct
3 Correct 27 ms 6904 KB Output is correct
4 Correct 20 ms 6904 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7032 KB Output is correct
2 Correct 33 ms 7032 KB Output is correct
3 Correct 26 ms 7032 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7676 KB Output is correct
2 Correct 59 ms 7812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7724 KB Output is correct
2 Correct 59 ms 7672 KB Output is correct