oj.uz

Submission #135069

# Submission time Handle Problem Language Result Execution time Memory
135069 2019-07-23T15:24:26 Z ryansee Strange Device (APIO19_strange_device) C++14
35 / 100
 702 ms 33116 KB 
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (1000006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = (ss); ii < (ll)(ee); ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define MSB(bm) ((bm==0)?-1:(63-__builtin_clzll((bm))))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
// #define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
// #define degug(...) 663
#define cerr if(0)cout
#endif
ll n,A,B;
pi E[MAXN];
ll limit=1e18+5;
ll qmult(ll x,ll e) {
	if(e==0)return 0;
	ll half=qmult(x,e/2);
	half+=half; half=min(half,limit);
	if(e&1) half+=x; half=min(half,limit);
	return half;
}
int main()
{
	FAST
	cin>>n>>A>>B;
	// ll p=qmult(A/gcd(A,B+1),B);
	ll p=A/gcd(A,B+1)*B;
	unsigned long long int test=((unsigned long long int)A) / ((unsigned long long int)gcd(A,B+1)) * ((unsigned long long int)B);
	if(p!=test) p=limit;
	FOR(i,0,n) cin>>E[i].f>>E[i].s; FOR(i,0,n) if(E[i].s-E[i].f+1>=p) { cout<<p<<'\n'; return 0; }
	vector<pi>pay;
	FOR(i,0,n) { ll a=E[i].f%p,b=E[i].s%p;
		if(a>b) pay.eb(a,p-1),pay.eb(0,b);
		else pay.eb(a,b);
	}
	sort(all(pay));
	ll px=-1; ll ans=0;
	for(auto i:pay) {
		if(px>=i.f) ans+=max(0ll,i.s-px);
		else ans+=i.s-i.f+1;
		px=max(px,i.s);
	}
	cout<<ans<<'\n';
}

Compilation message

strange_device.cpp: In function 'long long int qmult(long long int, long long int)':
strange_device.cpp:48:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(e&1) half+=x; half=min(half,limit);
  ^~
strange_device.cpp:48:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(e&1) half+=x; half=min(half,limit);
                   ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:58:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(p!=test) p=limit;
     ~^~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 1016 KB Output is correct
17 Correct 68 ms 4236 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 424 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 475 ms 33048 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 626 ms 33116 KB Output is correct
3 Correct 620 ms 32972 KB Output is correct
4 Correct 620 ms 33008 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 626 ms 33116 KB Output is correct
3 Correct 620 ms 32972 KB Output is correct
4 Correct 620 ms 33008 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 618 ms 32916 KB Output is correct
7 Correct 621 ms 32704 KB Output is correct
8 Correct 614 ms 33048 KB Output is correct
9 Correct 694 ms 32980 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 626 ms 33116 KB Output is correct
3 Correct 620 ms 32972 KB Output is correct
4 Correct 620 ms 33008 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 65 ms 4620 KB Output is correct
7 Correct 67 ms 4640 KB Output is correct
8 Correct 64 ms 4576 KB Output is correct
9 Correct 65 ms 4628 KB Output is correct
10 Correct 62 ms 4648 KB Output is correct
11 Correct 73 ms 4588 KB Output is correct
12 Correct 63 ms 4592 KB Output is correct
13 Correct 69 ms 4564 KB Output is correct
14 Correct 64 ms 4628 KB Output is correct
15 Correct 69 ms 4576 KB Output is correct
16 Correct 69 ms 4664 KB Output is correct
17 Correct 66 ms 4612 KB Output is correct
18 Correct 621 ms 32960 KB Output is correct
19 Correct 626 ms 32848 KB Output is correct
20 Correct 685 ms 32672 KB Output is correct
21 Correct 68 ms 4336 KB Output is correct
22 Correct 61 ms 4592 KB Output is correct
23 Correct 199 ms 15044 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 67 ms 4696 KB Output is correct
3 Correct 68 ms 4612 KB Output is correct
4 Correct 702 ms 33004 KB Output is correct
5 Correct 67 ms 4636 KB Output is correct
6 Correct 68 ms 4668 KB Output is correct
7 Correct 68 ms 4552 KB Output is correct
8 Correct 81 ms 4640 KB Output is correct
9 Correct 67 ms 4576 KB Output is correct
10 Correct 67 ms 4592 KB Output is correct
11 Correct 68 ms 4172 KB Output is correct
12 Correct 62 ms 4332 KB Output is correct
13 Correct 69 ms 4256 KB Output is correct
14 Correct 665 ms 32708 KB Output is correct
15 Correct 67 ms 4208 KB Output is correct
16 Correct 623 ms 32688 KB Output is correct
17 Correct 612 ms 32728 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 1016 KB Output is correct
17 Correct 68 ms 4236 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct