oj.uz

Submission #363982

# Submission time Handle Problem Language Result Execution time Memory
363982 2021-02-07T19:20:31 Z MahdiBahramian Strange Device (APIO19_strange_device) C++11
20 / 100
 2041 ms 122312 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const ll INF = 2e18 + 1000;
const int Max = 4e6 + 10;


ll L[Max] , R[Max];
vector<ll> compress;
unordered_map<ll , int> cnv;
int ps[Max];
int val[Max];
int main()
{
	ll n , A , B; cin >> n >> A >> B;
	ll SUM = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> L[i] >> R[i];
		SUM += R[i] - L[i] + 1;
	}
	if(A / __gcd(A , B + 1) > INF / B)
	{
		cout << SUM << '\n';
		return 0;
	}
	ll md = A * B / __gcd(A , B + 1);
	vector<pair<int , int>> vec;
	for(int i = 1 ; i <= n ; i++)
	{
		if(R[i] - L[i] + 1 >= md)
		{
			cout << md << '\n';
			return 0;
		}
		R[i] %= md;
		L[i] %= md;

		compress.pb(L[i]);
		compress.pb(R[i] + 1);
		if(R[i] < L[i])
		{
			vec.pb(mp(0 , R[i]));
			vec.pb(mp(L[i] , md - 1));
		}
		else vec.pb(mp(L[i] , R[i]));
	}
	compress.pb(0);
	compress.pb(md);
	sort(compress.begin() , compress.end());
	compress.resize(unique(compress.begin() , compress.end()) - compress.begin());
	for(int i = 0 ; i < compress.size() ; i++) cnv[compress[i]] = i;

	for(int i = 0 ; i < vec.size() ; i++)
	{
		//cout << vec[i].F << ',' << vec[i].S << '\n';
		val[cnv[vec[i].F]]++;
		val[cnv[vec[i].S + 1]]--;
	}
	for(int i = 1 ; i < compress.size() ; i++) val[i] += val[i - 1];
	ll res = 0;
	for(int i = 0 ; i < compress.size() - 1 ; i++)
	{
		if(val[i] >= 1)
		{
			res += compress[i + 1] - compress[i];
		}
	}
	cout << '\n';
	cout << res << '\n';
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0 ; i < compress.size() ; i++) cnv[compress[i]] = i;
      |                  ~~^~~~~~~~~~~~~~~~~
strange_device.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0 ; i < vec.size() ; i++)
      |                  ~~^~~~~~~~~~~~
strange_device.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 1 ; i < compress.size() ; i++) val[i] += val[i - 1];
      |                  ~~^~~~~~~~~~~~~~~~~
strange_device.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i = 0 ; i < compress.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 18 ms 1640 KB Output is correct
3 Correct 18 ms 1640 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 17 ms 1640 KB Output is correct
17 Correct 180 ms 12508 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 1158 ms 53956 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1765 ms 89524 KB Output is correct
3 Incorrect 2041 ms 122312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1765 ms 89524 KB Output is correct
3 Incorrect 2041 ms 122312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1765 ms 89524 KB Output is correct
3 Incorrect 2041 ms 122312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 183 ms 12508 KB Output is correct
3 Incorrect 199 ms 16696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 18 ms 1640 KB Output is correct
3 Correct 18 ms 1640 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 17 ms 1640 KB Output is correct
17 Correct 180 ms 12508 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 2 ms 492 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1158 ms 53956 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1765 ms 89524 KB Output is correct
31 Incorrect 2041 ms 122312 KB Output isn't correct
32 Halted 0 ms 0 KB -