oj.uz

Submission #932238

# Submission time Handle Problem Language Result Execution time Memory
932238 2024-02-23T06:08:48 Z Baizho Strange Device (APIO19_strange_device) C++14
65 / 100
 419 ms 36536 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 <= inf / b)	siz *= b;
	else siz = inf;
	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 348 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 4 ms 1116 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 1 ms 452 KB Output is correct
8 Correct 0 ms 348 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 34 ms 4044 KB Output is correct
18 Correct 0 ms 344 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 1 ms 344 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 344 KB Output is correct
2 Correct 1 ms 344 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 29448 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 303 ms 35092 KB Output is correct
3 Correct 317 ms 34840 KB Output is correct
4 Correct 298 ms 35072 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 303 ms 35092 KB Output is correct
3 Correct 317 ms 34840 KB Output is correct
4 Correct 298 ms 35072 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 307 ms 36096 KB Output is correct
7 Correct 303 ms 35512 KB Output is correct
8 Correct 298 ms 36124 KB Output is correct
9 Correct 327 ms 36280 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 303 ms 35092 KB Output is correct
3 Correct 317 ms 34840 KB Output is correct
4 Correct 298 ms 35072 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 30 ms 4556 KB Output is correct
7 Correct 33 ms 4564 KB Output is correct
8 Correct 29 ms 4564 KB Output is correct
9 Correct 30 ms 4568 KB Output is correct
10 Correct 30 ms 4556 KB Output is correct
11 Correct 31 ms 4788 KB Output is correct
12 Correct 29 ms 4560 KB Output is correct
13 Correct 32 ms 4568 KB Output is correct
14 Correct 29 ms 4564 KB Output is correct
15 Correct 33 ms 4568 KB Output is correct
16 Correct 32 ms 4488 KB Output is correct
17 Correct 38 ms 4560 KB Output is correct
18 Correct 317 ms 36536 KB Output is correct
19 Correct 311 ms 34984 KB Output is correct
20 Correct 351 ms 34900 KB Output is correct
21 Correct 43 ms 4564 KB Output is correct
22 Correct 43 ms 4560 KB Output is correct
23 Correct 97 ms 17092 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 34 ms 4564 KB Output is correct
3 Correct 37 ms 4516 KB Output is correct
4 Correct 419 ms 35696 KB Output is correct
5 Correct 34 ms 4236 KB Output is correct
6 Correct 37 ms 4568 KB Output is correct
7 Correct 41 ms 4512 KB Output is correct
8 Correct 50 ms 4560 KB Output is correct
9 Correct 42 ms 4560 KB Output is correct
10 Correct 33 ms 4672 KB Output is correct
11 Correct 33 ms 4568 KB Output is correct
12 Correct 28 ms 4560 KB Output is correct
13 Correct 32 ms 4636 KB Output is correct
14 Correct 333 ms 34860 KB Output is correct
15 Correct 36 ms 4560 KB Output is correct
16 Correct 296 ms 36532 KB Output is correct
17 Correct 289 ms 36020 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 348 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 4 ms 1116 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 1 ms 452 KB Output is correct
8 Correct 0 ms 348 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 34 ms 4044 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 1 ms 344 KB Output isn't correct
21 Halted 0 ms 0 KB -