oj.uz

Submission #932218

# Submission time Handle Problem Language Result Execution time Memory
932218 2024-02-23T05:43:02 Z Baizho Strange Device (APIO19_strange_device) C++14
65 / 100
 407 ms 54412 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) * b;
	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 856 KB Output is correct
3 Correct 4 ms 736 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 3 ms 736 KB Output is correct
17 Correct 42 ms 2768 KB Output is correct
18 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 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 214 ms 18548 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 380 ms 18684 KB Output is correct
3 Correct 320 ms 53264 KB Output is correct
4 Correct 321 ms 53372 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 380 ms 18684 KB Output is correct
3 Correct 320 ms 53264 KB Output is correct
4 Correct 321 ms 53372 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 314 ms 53352 KB Output is correct
7 Correct 307 ms 53344 KB Output is correct
8 Correct 309 ms 53340 KB Output is correct
9 Correct 349 ms 53364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 380 ms 18684 KB Output is correct
3 Correct 320 ms 53264 KB Output is correct
4 Correct 321 ms 53372 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 43 ms 5668 KB Output is correct
7 Correct 34 ms 5800 KB Output is correct
8 Correct 33 ms 5800 KB Output is correct
9 Correct 31 ms 5844 KB Output is correct
10 Correct 36 ms 5776 KB Output is correct
11 Correct 34 ms 5836 KB Output is correct
12 Correct 33 ms 5820 KB Output is correct
13 Correct 37 ms 5748 KB Output is correct
14 Correct 31 ms 5808 KB Output is correct
15 Correct 36 ms 5832 KB Output is correct
16 Correct 34 ms 5828 KB Output is correct
17 Correct 32 ms 5612 KB Output is correct
18 Correct 331 ms 53316 KB Output is correct
19 Correct 316 ms 53372 KB Output is correct
20 Correct 356 ms 53324 KB Output is correct
21 Correct 44 ms 5680 KB Output is correct
22 Correct 32 ms 5696 KB Output is correct
23 Correct 112 ms 20392 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 35 ms 5844 KB Output is correct
3 Correct 34 ms 5644 KB Output is correct
4 Correct 407 ms 53232 KB Output is correct
5 Correct 34 ms 5820 KB Output is correct
6 Correct 40 ms 5632 KB Output is correct
7 Correct 33 ms 5836 KB Output is correct
8 Correct 41 ms 5840 KB Output is correct
9 Correct 35 ms 5652 KB Output is correct
10 Correct 33 ms 5832 KB Output is correct
11 Correct 35 ms 5816 KB Output is correct
12 Correct 29 ms 5720 KB Output is correct
13 Correct 38 ms 5752 KB Output is correct
14 Correct 407 ms 53632 KB Output is correct
15 Correct 35 ms 5836 KB Output is correct
16 Correct 330 ms 53688 KB Output is correct
17 Correct 329 ms 54412 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 856 KB Output is correct
3 Correct 4 ms 736 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 3 ms 736 KB Output is correct
17 Correct 42 ms 2768 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -