oj.uz

Submission #135078

# Submission time Handle Problem Language Result Execution time Memory
135078 2019-07-23T15:34:52 Z ryansee Strange Device (APIO19_strange_device) C++14
35 / 100
 711 ms 33188 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);
	assert(p>0); if(p!=test) p=limit; //or p<test, or don't handle also can,cos p will be neg,and the E[i].s-E[i].f+1 >= p will pass, also the qmult works
	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:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(p>0); if(p!=test) p=limit; //or p<test, or don't handle also can,cos p will be neg,and the E[i].s-E[i].f+1 >= p will pass, also the qmult works
                  ~^~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 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 376 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 1144 KB Output is correct
17 Correct 68 ms 4560 KB Output is correct
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

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 400 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 448 ms 32796 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 615 ms 32832 KB Output is correct
3 Correct 632 ms 33020 KB Output is correct
4 Correct 611 ms 33064 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 615 ms 32832 KB Output is correct
3 Correct 632 ms 33020 KB Output is correct
4 Correct 611 ms 33064 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 631 ms 33060 KB Output is correct
7 Correct 612 ms 33040 KB Output is correct
8 Correct 610 ms 32944 KB Output is correct
9 Correct 673 ms 32848 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 615 ms 32832 KB Output is correct
3 Correct 632 ms 33020 KB Output is correct
4 Correct 611 ms 33064 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 62 ms 4368 KB Output is correct
7 Correct 68 ms 4636 KB Output is correct
8 Correct 66 ms 4488 KB Output is correct
9 Correct 64 ms 4332 KB Output is correct
10 Correct 61 ms 4336 KB Output is correct
11 Correct 64 ms 4336 KB Output is correct
12 Correct 62 ms 4352 KB Output is correct
13 Correct 67 ms 4324 KB Output is correct
14 Correct 62 ms 4348 KB Output is correct
15 Correct 68 ms 4304 KB Output is correct
16 Correct 76 ms 4496 KB Output is correct
17 Correct 65 ms 4592 KB Output is correct
18 Correct 659 ms 33132 KB Output is correct
19 Correct 618 ms 33104 KB Output is correct
20 Correct 711 ms 33188 KB Output is correct
21 Correct 67 ms 4720 KB Output is correct
22 Correct 66 ms 4628 KB Output is correct
23 Correct 198 ms 15136 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 4740 KB Output is correct
3 Correct 67 ms 4672 KB Output is correct
4 Correct 696 ms 32860 KB Output is correct
5 Correct 67 ms 4636 KB Output is correct
6 Correct 67 ms 4592 KB Output is correct
7 Correct 66 ms 4588 KB Output is correct
8 Correct 71 ms 4568 KB Output is correct
9 Correct 66 ms 4304 KB Output is correct
10 Correct 67 ms 4336 KB Output is correct
11 Correct 67 ms 4404 KB Output is correct
12 Correct 60 ms 4332 KB Output is correct
13 Correct 66 ms 4332 KB Output is correct
14 Correct 661 ms 32928 KB Output is correct
15 Correct 66 ms 4592 KB Output is correct
16 Correct 608 ms 33128 KB Output is correct
17 Correct 604 ms 33028 KB Output is correct
18 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 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 376 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 1144 KB Output is correct
17 Correct 68 ms 4560 KB Output is correct
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)