oj.uz

Submission #1035272

# Submission time Handle Problem Language Result Execution time Memory
1035272 2024-07-26T08:33:17 Z KasymK Strange Device (APIO19_strange_device) C++17
0 / 100
 0 ms 348 KB 
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int N = 1e6+5;
ll l[N], r[N];

int main(){
	int n;
	ll a, b;
	scanf("%d %lld %lld", &n, &a, &b);
	__int128 m = (__int128)a/__gcd(a, b+1)*b;
	for(int i = 1 ; i <= n; ++i)
		scanf("%lld %lld", &l[i], &r[i]);
	vector<pll> v;
	for(int i = 1; i <= n; ++i){
		if(r[i]-l[i]+1 >= m)
			v.pb({0, -1});
		else if(l[i]%m > r[i]%m)
			v.pb({l[i]%m, m-1}), v.pb({0, r[i]%m});
		else
			v.pb({l[i]%m, r[i]%m});
	}
	sort(all(v));
	ll l_ = v.front().ff, r_ = v.front().ss;
	ll answer = 0;
	int n_ = (int)v.size();
	for(int i = 0; i < n_; ++i){
		// I am doing kerim's technique instead of sweep line
		// because Kerim's technique is O(n), but sweep line is O(nlog(n)) in worst case
		// because in sweep line we use like set data structure's
		if(v[i].ff <= r_)
			umax(r_, v[i].ss);
		else
			answer += (r_-l_+1), l_ = v[i].ff, r_ = v[i].ss;
	}
	answer += (r_-l_+1);
	printf("%lld\n", answer);
	return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -