oj.uz

답안 #135063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135063 2019-07-23T15:14:00 Z ryansee 이상한 기계 (APIO19_strange_device) C++14
65 / 100
 713 ms 34376 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);
	FOR(i,0,n) cin>>E[i].f>>E[i].s;
	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);
                   ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1324 KB Output is correct
3 Correct 9 ms 1272 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 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 1 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 1 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 9 ms 1272 KB Output is correct
17 Correct 72 ms 5916 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 460 ms 34376 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 651 ms 33832 KB Output is correct
3 Correct 631 ms 33856 KB Output is correct
4 Correct 633 ms 34132 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 651 ms 33832 KB Output is correct
3 Correct 631 ms 33856 KB Output is correct
4 Correct 633 ms 34132 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 618 ms 33836 KB Output is correct
7 Correct 619 ms 33764 KB Output is correct
8 Correct 616 ms 33836 KB Output is correct
9 Correct 688 ms 33732 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 651 ms 33832 KB Output is correct
3 Correct 631 ms 33856 KB Output is correct
4 Correct 633 ms 34132 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 63 ms 5100 KB Output is correct
7 Correct 67 ms 5360 KB Output is correct
8 Correct 62 ms 5360 KB Output is correct
9 Correct 64 ms 5312 KB Output is correct
10 Correct 62 ms 5644 KB Output is correct
11 Correct 66 ms 5588 KB Output is correct
12 Correct 63 ms 5620 KB Output is correct
13 Correct 68 ms 5616 KB Output is correct
14 Correct 62 ms 5748 KB Output is correct
15 Correct 69 ms 5744 KB Output is correct
16 Correct 100 ms 5748 KB Output is correct
17 Correct 66 ms 5716 KB Output is correct
18 Correct 622 ms 33720 KB Output is correct
19 Correct 612 ms 34092 KB Output is correct
20 Correct 679 ms 33864 KB Output is correct
21 Correct 70 ms 6352 KB Output is correct
22 Correct 63 ms 5856 KB Output is correct
23 Correct 207 ms 17224 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 68 ms 5772 KB Output is correct
3 Correct 70 ms 6180 KB Output is correct
4 Correct 713 ms 33884 KB Output is correct
5 Correct 69 ms 5668 KB Output is correct
6 Correct 69 ms 5620 KB Output is correct
7 Correct 69 ms 5536 KB Output is correct
8 Correct 69 ms 5460 KB Output is correct
9 Correct 68 ms 5532 KB Output is correct
10 Correct 68 ms 5692 KB Output is correct
11 Correct 69 ms 5740 KB Output is correct
12 Correct 61 ms 5748 KB Output is correct
13 Correct 69 ms 5716 KB Output is correct
14 Correct 676 ms 33932 KB Output is correct
15 Correct 68 ms 6144 KB Output is correct
16 Correct 615 ms 33952 KB Output is correct
17 Correct 606 ms 33920 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1324 KB Output is correct
3 Correct 9 ms 1272 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 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 1 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 1 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 9 ms 1272 KB Output is correct
17 Correct 72 ms 5916 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Incorrect 2 ms 376 KB Output isn't correct
21 Halted 0 ms 0 KB -