oj.uz

Submission #55401

# Submission time Handle Problem Language Result Execution time Memory
55401 2018-07-07T07:46:09 Z 김세빈(#1545) Toilets (JOI16_toilets) C++11
14 / 100
 1000 ms 5940 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

char str[202020];
ll K[202020];
ll T[606060], L[606060];
ll n, k, f, m, sz;

void add(ll p, ll s, ll e, ll l, ll r)
{
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		L[p] ++;
		return;
	}
	
	L[p<<1] += L[p], L[p<<1|1] += L[p];
	L[p] = 0;
	
	add(p<<1, s, s+e>>1, l, r);
	add(p<<1|1, (s+e>>1)+1, e, l, r);
	
	T[p] = max(T[p<<1] + L[p<<1], T[p<<1|1] + L[p<<1|1]);
}

ll get_max(ll p, ll s, ll e, ll l, ll r)
{
	if(r < s || e < l) return -1;
	if(l <= s && e <= r) return T[p] + L[p];
	
	L[p<<1] += L[p], L[p<<1|1] += L[p];
	L[p] = 0;
	
	ll ret = max(get_max(p<<1, s, s+e>>1, l, r), get_max(p<<1|1, (s+e>>1)+1, e, l, r));
	
	T[p] = max(T[p<<1] + L[p<<1], T[p<<1|1] + L[p<<1|1]);
	
	return ret;
}

bool check(ll k)
{
	ll i, a, b;
	
	for(i=0;i<sz+sz;i++) T[i] = L[i] = 0;
	
	a = b = 0;
	
	for(i=0;i<n+n;i++){
		if(a < m && ((~i & 1) || f - b >= m - (a+1)) && get_max(1, 0, sz-1, b+1, K[a+1]) < k){
			add(1, 0, sz-1, b+1, K[a+1]);
			a ++;
		}
		else if(b < f && ((~i & 1) || f - (b+1) >= m - a)) b ++;
		else return 0;
	}
	
	return 1;
}

int main()
{
	ll i, s, e;
	
	scanf("%lld%lld", &n, &k);
	
	if(k > 1) return 0;
	
	scanf("%s", str);
	
	for(i=0;i<n+n;i++){
		if(str[i] == 'F') f ++;
		else{
			m ++;
			K[m] = f;
		}
	}
	
	if(f < m){
		printf("-1\n");
		return 0;
	}
	
	for(sz=1;sz<=f;sz<<=1);
	
	for(s=0,e=n+n;s<=e;){
		if(check(s+e>>1)) e = (s+e>>1) - 1;
		else s = (s+e>>1) + 1;
	}
	
	printf("%lld\n", e + 1);
	
	return 0;
}

Compilation message

toilets.cpp: In function 'void add(ll, ll, ll, ll, ll)':
toilets.cpp:23:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1, s, s+e>>1, l, r);
               ~^~
toilets.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1|1, (s+e>>1)+1, e, l, r);
               ~^~
toilets.cpp: In function 'll get_max(ll, ll, ll, ll, ll)':
toilets.cpp:37:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll ret = max(get_max(p<<1, s, s+e>>1, l, r), get_max(p<<1|1, (s+e>>1)+1, e, l, r));
                                ~^~
toilets.cpp:37:65: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll ret = max(get_max(p<<1, s, s+e>>1, l, r), get_max(p<<1|1, (s+e>>1)+1, e, l, r));
                                                                ~^~
toilets.cpp: In function 'int main()':
toilets.cpp:90:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) e = (s+e>>1) - 1;
            ~^~
toilets.cpp:90:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) e = (s+e>>1) - 1;
                          ~^~
toilets.cpp:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else s = (s+e>>1) + 1;
             ~^~
toilets.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
toilets.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str);
  ~~~~~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 900 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 3 ms 900 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 3 ms 900 KB Output is correct
21 Correct 3 ms 900 KB Output is correct
22 Correct 3 ms 900 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 900 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 3 ms 900 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 3 ms 900 KB Output is correct
21 Correct 3 ms 900 KB Output is correct
22 Correct 3 ms 900 KB Output is correct
23 Execution timed out 1071 ms 5940 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 4 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 900 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 3 ms 900 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 3 ms 900 KB Output is correct
21 Correct 3 ms 900 KB Output is correct
22 Correct 3 ms 900 KB Output is correct
23 Execution timed out 1071 ms 5940 KB Time limit exceeded
24 Halted 0 ms 0 KB -