oj.uz

Submission #932226

# Submission time Handle Problem Language Result Execution time Memory
932226 2024-02-23T05:50:30 Z Baizho Strange Device (APIO19_strange_device) C++14
10 / 100
 399 ms 18872 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(2e3)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
 
#define int ll

bool comp(pair<int, int> a, pair<int, int> b) {
	if(a.ss == b.ss) return a.ff > b.ff;
	return a.ss < b.ss;
}

void Baizho() {
	int n, a, b; cin>>n>>a>>b;
	int siz = a / __gcd(a, b + 1);
	if(siz <= 1LL * 2e18 / b)	siz *= b;
	else siz = 2e18;
	vector<pair<int, int> > range;
	while(n --) {
		int l, r; cin>>l>>r;
		l %= siz; r %= siz;
		if(l <= r) {
			range.pb({l, r});
		} else {
			range.pb({0, r});
			range.pb({l, siz - 1});
		}
	}
	sort(all(range), comp);
	int maxr = -1, ans = 0;
	for(auto c : range) {
		if(maxr < c.ff) {
			// new segment started
			ans += c.ss - c.ff + 1;
			maxr = c.ss;
		} else if(c.ff <= maxr && maxr <= c.ss) {
			// not completely new
			ans += c.ss - maxr;
			maxr = c.ss;
		}
	}
	cout<<ans<<"\n";
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

strange_device.cpp: In function 'void Freopen(std::string)':
strange_device.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 17996 KB Output is correct
3 Correct 336 ms 17548 KB Output is correct
4 Correct 327 ms 18644 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 17996 KB Output is correct
3 Correct 336 ms 17548 KB Output is correct
4 Correct 327 ms 18644 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 389 ms 18504 KB Output is correct
7 Correct 336 ms 17384 KB Output is correct
8 Correct 334 ms 18704 KB Output is correct
9 Correct 381 ms 18872 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 17996 KB Output is correct
3 Correct 336 ms 17548 KB Output is correct
4 Correct 327 ms 18644 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 34 ms 2452 KB Output is correct
7 Correct 35 ms 2520 KB Output is correct
8 Correct 33 ms 2520 KB Output is correct
9 Correct 34 ms 2520 KB Output is correct
10 Correct 35 ms 2520 KB Output is correct
11 Correct 35 ms 2520 KB Output is correct
12 Correct 32 ms 2520 KB Output is correct
13 Correct 37 ms 2532 KB Output is correct
14 Correct 32 ms 3544 KB Output is correct
15 Incorrect 47 ms 2604 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 43 ms 2520 KB Output is correct
3 Correct 37 ms 2516 KB Output is correct
4 Correct 399 ms 18620 KB Output is correct
5 Correct 36 ms 2520 KB Output is correct
6 Correct 36 ms 2520 KB Output is correct
7 Correct 37 ms 2440 KB Output is correct
8 Correct 38 ms 2520 KB Output is correct
9 Correct 36 ms 2520 KB Output is correct
10 Correct 36 ms 2520 KB Output is correct
11 Correct 36 ms 2516 KB Output is correct
12 Correct 30 ms 2520 KB Output is correct
13 Correct 36 ms 2520 KB Output is correct
14 Incorrect 390 ms 18872 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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