oj.uz

Submission #122791

# Submission time Handle Problem Language Result Execution time Memory
122791 2019-06-29T09:30:28 Z abacaba Strange Device (APIO19_strange_device) C++14
35 / 100
 892 ms 39916 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 15;
int n;
long long t, a, b, l, r, ans;
vector <pair <long long, int> > temp;
stack <long long> st;

int main() {
	scanf("%d%lld%lld", &n, &a, &b);
	if((b + 1) % a == 0)
		t = b;
	else {
		t = a / __gcd(a, b + 1);
		t *= b;
	}
	while(n--) {
		scanf("%lld%lld", &l, &r);
		if(r - l + 1 >= t)
			return cout << t, 0;
		l %= t, r %= t;
		if(l > r) {
			temp.push_back({l, -1});
			temp.push_back({t, 1});
			temp.push_back({0, -1});
			temp.push_back({r + 1, 1});
		}
		else {
			temp.push_back({l, -1});
			temp.push_back({r + 1, 1});
		}
	}
	sort(temp.begin(), temp.end());
	for(auto i : temp) {
		if(i.second == 1) {
			if(st.size() == 1)
				ans += i.first - st.top();
			st.pop();
		}
		else
			st.push(i.first);
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 9 ms 1012 KB Output is correct
3 Correct 9 ms 1012 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1012 KB Output is correct
17 Correct 80 ms 4580 KB Output is correct
18 Incorrect 3 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 535 ms 39916 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 667 ms 33320 KB Output is correct
3 Correct 720 ms 33212 KB Output is correct
4 Correct 682 ms 33208 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 667 ms 33320 KB Output is correct
3 Correct 720 ms 33212 KB Output is correct
4 Correct 682 ms 33208 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 688 ms 33268 KB Output is correct
7 Correct 678 ms 33220 KB Output is correct
8 Correct 694 ms 33212 KB Output is correct
9 Correct 802 ms 33336 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 667 ms 33320 KB Output is correct
3 Correct 720 ms 33212 KB Output is correct
4 Correct 682 ms 33208 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 66 ms 4584 KB Output is correct
7 Correct 71 ms 4580 KB Output is correct
8 Correct 65 ms 4620 KB Output is correct
9 Correct 69 ms 4580 KB Output is correct
10 Correct 63 ms 4628 KB Output is correct
11 Correct 70 ms 4588 KB Output is correct
12 Correct 62 ms 4452 KB Output is correct
13 Correct 71 ms 4580 KB Output is correct
14 Correct 65 ms 4616 KB Output is correct
15 Correct 79 ms 4580 KB Output is correct
16 Correct 77 ms 4584 KB Output is correct
17 Correct 66 ms 4580 KB Output is correct
18 Correct 697 ms 33332 KB Output is correct
19 Correct 664 ms 33412 KB Output is correct
20 Correct 836 ms 33332 KB Output is correct
21 Correct 80 ms 4500 KB Output is correct
22 Correct 62 ms 4580 KB Output is correct
23 Correct 231 ms 16916 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 75 ms 4580 KB Output is correct
3 Correct 77 ms 4580 KB Output is correct
4 Correct 892 ms 33400 KB Output is correct
5 Correct 77 ms 4580 KB Output is correct
6 Correct 77 ms 4564 KB Output is correct
7 Correct 81 ms 4580 KB Output is correct
8 Correct 78 ms 4580 KB Output is correct
9 Correct 74 ms 4580 KB Output is correct
10 Correct 80 ms 4552 KB Output is correct
11 Correct 76 ms 4580 KB Output is correct
12 Correct 69 ms 4580 KB Output is correct
13 Correct 79 ms 4580 KB Output is correct
14 Correct 802 ms 33348 KB Output is correct
15 Correct 79 ms 4580 KB Output is correct
16 Correct 657 ms 33288 KB Output is correct
17 Correct 688 ms 33348 KB Output is correct
18 Incorrect 2 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 9 ms 1012 KB Output is correct
3 Correct 9 ms 1012 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1012 KB Output is correct
17 Correct 80 ms 4580 KB Output is correct
18 Incorrect 3 ms 376 KB Output isn't correct