oj.uz

Submission #135073

# Submission time Handle Problem Language Result Execution time Memory
135073 2019-07-23T15:26:08 Z ryansee Strange Device (APIO19_strange_device) C++14
35 / 100
 733 ms 32660 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:57:25: warning: unused variable 'test' [-Wunused-variable]
  unsigned long long int test=((unsigned long long int)A) / ((unsigned long long int)gcd(A,B+1)) * ((unsigned long long int)B);
                         ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 8 ms 860 KB Output is correct
3 Correct 9 ms 880 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 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 380 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 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 988 KB Output is correct
17 Correct 68 ms 4364 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 2 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 376 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 476 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 451 ms 32528 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 616 ms 32636 KB Output is correct
3 Correct 613 ms 32516 KB Output is correct
4 Correct 625 ms 32544 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 616 ms 32636 KB Output is correct
3 Correct 613 ms 32516 KB Output is correct
4 Correct 625 ms 32544 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 610 ms 32652 KB Output is correct
7 Correct 670 ms 32660 KB Output is correct
8 Correct 612 ms 32604 KB Output is correct
9 Correct 697 ms 32544 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 616 ms 32636 KB Output is correct
3 Correct 613 ms 32516 KB Output is correct
4 Correct 625 ms 32544 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 67 ms 4384 KB Output is correct
7 Correct 68 ms 4280 KB Output is correct
8 Correct 64 ms 4340 KB Output is correct
9 Correct 64 ms 4420 KB Output is correct
10 Correct 61 ms 4064 KB Output is correct
11 Correct 64 ms 4092 KB Output is correct
12 Correct 61 ms 4112 KB Output is correct
13 Correct 67 ms 4108 KB Output is correct
14 Correct 61 ms 4212 KB Output is correct
15 Correct 69 ms 4336 KB Output is correct
16 Correct 68 ms 4464 KB Output is correct
17 Correct 64 ms 4336 KB Output is correct
18 Correct 636 ms 32572 KB Output is correct
19 Correct 611 ms 32532 KB Output is correct
20 Correct 704 ms 32640 KB Output is correct
21 Correct 66 ms 4336 KB Output is correct
22 Correct 61 ms 4408 KB Output is correct
23 Correct 192 ms 14108 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 67 ms 4140 KB Output is correct
3 Correct 67 ms 4080 KB Output is correct
4 Correct 705 ms 32560 KB Output is correct
5 Correct 67 ms 4152 KB Output is correct
6 Correct 69 ms 4124 KB Output is correct
7 Correct 62 ms 4096 KB Output is correct
8 Correct 70 ms 4080 KB Output is correct
9 Correct 67 ms 4080 KB Output is correct
10 Correct 67 ms 4052 KB Output is correct
11 Correct 67 ms 4108 KB Output is correct
12 Correct 60 ms 4076 KB Output is correct
13 Correct 67 ms 4080 KB Output is correct
14 Correct 733 ms 32520 KB Output is correct
15 Correct 68 ms 4076 KB Output is correct
16 Correct 606 ms 32524 KB Output is correct
17 Correct 600 ms 32528 KB Output is correct
18 Incorrect 0 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 8 ms 860 KB Output is correct
3 Correct 9 ms 880 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 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 380 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 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 988 KB Output is correct
17 Correct 68 ms 4364 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct