oj.uz

Submission #135407

# Submission time Handle Problem Language Result Execution time Memory
135407 2019-07-24T04:58:24 Z 김세빈(#3248) MP3 Player (CEOI10_mp3player) C++14
100 / 100
 75 ms 5144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

struct node{
	int l, r, v;
	
	node() {}
	node(int l, int r, int v) :
		l(l - min(0, v)), r(r - max(0, v)), v(v) {}
	
	node operator + (node n)
	{
		node ret;
		
		if(r + v < n.l){
			ret.l = ret.r = r;
			ret.v = n.l + n.v - r;
		}
		else if(l + v > n.r){
			ret.l = ret.r = l;
			ret.v = n.r + n.v - l;
		}
		else{
			ret.l = max(l, n.l - v);
			ret.r = min(r, n.r - v);
			ret.v = v + n.v;
		}
		
		return ret;
	}
};

struct segtree{
	node T[303030];
	
	void update(int p, int s, int e, int v, node x)
	{
		if(s == e) T[p] = x;
		else{
			if(v <= (s + e >> 1)){
				update(p << 1, s, (s + e >> 1), v, x);
			}
			else{
				update(p << 1 | 1, (s + e >> 1) + 1, e, v, x);
			}
			T[p] = T[p << 1] + T[p << 1 | 1];
		}
	}
	
	int check(int k, int m)
	{
		if(T[1].l + T[1].v > k || T[1].r + T[1].v < k) return -1;
		else if(T[1].r + T[1].v == k) return m;
		else return k - T[1].v;
	}
	
};

segtree T;
vector <pii> K;
int X[101010], V[101010];
int n, m, k;

int main()
{
	char S[3];
	int i, j, t;
	
	scanf("%d%d%d", &n, &m, &k);
	
	for(i=0; i<n; i++){
		scanf("%s%d", S, X + i);
		if(*S == '+') V[i] = 1;
		else V[i] = -1;
	}
	
	for(i=1; i<n; i++){
		K.emplace_back(X[i] - X[i - 1], i);
		T.update(1, 1, n - 1, i, node(0, m, V[i]));
	}
	
	if(T.check(k, m) != -1){
		printf("infinity\n");
		return 0;
	}
	
	sort(K.rbegin(), K.rend());
	
	for(i=0; i<n-1; i=j){
		for(j=i; j<n-1 && K[i].first == K[j].first; j++){
			T.update(1, 1, n - 1, K[j].second, node(0, m, 0));
		}
		
		t = T.check(k, m);
		if(t != -1){
			printf("%d %d\n", K[i].first - 1, t);
			return 0;
		}
	}
	
	return 0;
}

Compilation message

mp3player.cpp: In member function 'void segtree::update(int, int, int, int, node)':
mp3player.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(v <= (s + e >> 1)){
             ~~^~~
mp3player.cpp:44:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     update(p << 1, s, (s + e >> 1), v, x);
                        ~~^~~
mp3player.cpp:47:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     update(p << 1 | 1, (s + e >> 1) + 1, e, v, x);
                         ~~^~~
mp3player.cpp: In function 'int main()':
mp3player.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", S, X + 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 3 ms 504 KB Output is correct
2 Correct 4 ms 532 KB Output is correct
3 Correct 4 ms 504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 552 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 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 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1528 KB Output is correct
2 Correct 16 ms 1528 KB Output is correct
3 Correct 17 ms 1652 KB Output is correct
4 Correct 14 ms 1528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1652 KB Output is correct
2 Correct 18 ms 1652 KB Output is correct
3 Correct 18 ms 1656 KB Output is correct
4 Correct 14 ms 1524 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1652 KB Output is correct
2 Correct 14 ms 1780 KB Output is correct
3 Correct 25 ms 2676 KB Output is correct
4 Correct 17 ms 1652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2756 KB Output is correct
2 Correct 34 ms 2672 KB Output is correct
3 Correct 26 ms 2640 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 5120 KB Output is correct
2 Correct 65 ms 5140 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5144 KB Output is correct
2 Correct 68 ms 5100 KB Output is correct