oj.uz

Submission #932222

# Submission time Handle Problem Language Result Execution time Memory
932222 2024-02-23T05:47:08 Z Baizho Strange Device (APIO19_strange_device) C++14
65 / 100
 389 ms 18676 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

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));
	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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 736 KB Output is correct
3 Correct 3 ms 736 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 736 KB Output is correct
17 Correct 37 ms 2732 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 204 ms 18292 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 293 ms 17152 KB Output is correct
3 Correct 286 ms 17644 KB Output is correct
4 Correct 309 ms 18332 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 293 ms 17152 KB Output is correct
3 Correct 286 ms 17644 KB Output is correct
4 Correct 309 ms 18332 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 293 ms 17648 KB Output is correct
7 Correct 298 ms 17256 KB Output is correct
8 Correct 286 ms 18356 KB Output is correct
9 Correct 344 ms 18100 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 293 ms 17152 KB Output is correct
3 Correct 286 ms 17644 KB Output is correct
4 Correct 309 ms 18332 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 28 ms 2520 KB Output is correct
7 Correct 33 ms 2520 KB Output is correct
8 Correct 29 ms 2596 KB Output is correct
9 Correct 30 ms 2520 KB Output is correct
10 Correct 32 ms 2520 KB Output is correct
11 Correct 30 ms 2516 KB Output is correct
12 Correct 28 ms 2516 KB Output is correct
13 Correct 31 ms 2452 KB Output is correct
14 Correct 31 ms 2516 KB Output is correct
15 Correct 33 ms 2516 KB Output is correct
16 Correct 34 ms 2520 KB Output is correct
17 Correct 38 ms 2520 KB Output is correct
18 Correct 313 ms 17364 KB Output is correct
19 Correct 293 ms 18584 KB Output is correct
20 Correct 320 ms 17848 KB Output is correct
21 Correct 33 ms 2516 KB Output is correct
22 Correct 27 ms 2520 KB Output is correct
23 Correct 86 ms 8636 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 2520 KB Output is correct
3 Correct 32 ms 2516 KB Output is correct
4 Correct 389 ms 18468 KB Output is correct
5 Correct 35 ms 2508 KB Output is correct
6 Correct 31 ms 2520 KB Output is correct
7 Correct 35 ms 2520 KB Output is correct
8 Correct 33 ms 2520 KB Output is correct
9 Correct 32 ms 2612 KB Output is correct
10 Correct 32 ms 2520 KB Output is correct
11 Correct 32 ms 2520 KB Output is correct
12 Correct 27 ms 2520 KB Output is correct
13 Correct 32 ms 3612 KB Output is correct
14 Correct 320 ms 17756 KB Output is correct
15 Correct 31 ms 2516 KB Output is correct
16 Correct 299 ms 18676 KB Output is correct
17 Correct 285 ms 17508 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 736 KB Output is correct
3 Correct 3 ms 736 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 736 KB Output is correct
17 Correct 37 ms 2732 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -