oj.uz

답안 #135077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135077 2019-07-23T15:33:30 Z ryansee 이상한 기계 (APIO19_strange_device) C++14
35 / 100
 776 ms 33676 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; //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:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 1272 KB Output is correct
3 Correct 9 ms 1272 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 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 0 ms 1276 KB Output is correct
17 Correct 71 ms 6140 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 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 380 KB Output isn't correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 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 504 KB Output is correct
5 Correct 509 ms 33596 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 652 ms 33536 KB Output is correct
3 Correct 617 ms 33556 KB Output is correct
4 Correct 623 ms 33676 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 652 ms 33536 KB Output is correct
3 Correct 617 ms 33556 KB Output is correct
4 Correct 623 ms 33676 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 616 ms 33536 KB Output is correct
7 Correct 615 ms 33528 KB Output is correct
8 Correct 616 ms 33368 KB Output is correct
9 Correct 673 ms 33624 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 652 ms 33536 KB Output is correct
3 Correct 617 ms 33556 KB Output is correct
4 Correct 623 ms 33676 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 64 ms 6476 KB Output is correct
7 Correct 66 ms 6292 KB Output is correct
8 Correct 65 ms 6428 KB Output is correct
9 Correct 68 ms 6336 KB Output is correct
10 Correct 63 ms 5588 KB Output is correct
11 Correct 66 ms 5616 KB Output is correct
12 Correct 64 ms 5664 KB Output is correct
13 Correct 69 ms 5616 KB Output is correct
14 Correct 62 ms 5760 KB Output is correct
15 Correct 70 ms 5488 KB Output is correct
16 Correct 68 ms 5616 KB Output is correct
17 Correct 65 ms 5484 KB Output is correct
18 Correct 620 ms 33344 KB Output is correct
19 Correct 638 ms 33360 KB Output is correct
20 Correct 682 ms 33316 KB Output is correct
21 Correct 69 ms 6044 KB Output is correct
22 Correct 64 ms 5788 KB Output is correct
23 Correct 203 ms 17512 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 68 ms 5324 KB Output is correct
3 Correct 80 ms 5076 KB Output is correct
4 Correct 776 ms 33412 KB Output is correct
5 Correct 68 ms 5576 KB Output is correct
6 Correct 68 ms 5488 KB Output is correct
7 Correct 69 ms 5560 KB Output is correct
8 Correct 70 ms 5576 KB Output is correct
9 Correct 69 ms 5812 KB Output is correct
10 Correct 70 ms 5716 KB Output is correct
11 Correct 68 ms 5876 KB Output is correct
12 Correct 63 ms 6032 KB Output is correct
13 Correct 68 ms 5868 KB Output is correct
14 Correct 672 ms 33572 KB Output is correct
15 Correct 70 ms 6020 KB Output is correct
16 Correct 637 ms 33392 KB Output is correct
17 Correct 670 ms 33400 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 1272 KB Output is correct
3 Correct 9 ms 1272 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 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 0 ms 1276 KB Output is correct
17 Correct 71 ms 6140 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct