oj.uz

Submission #230057

# Submission time Handle Problem Language Result Execution time Memory
230057 2020-05-07T23:31:45 Z AMO5 Strange Device (APIO19_strange_device) C++
35 / 100
 703 ms 37472 KB 
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=1e6+5;

ll l[mxn],r[mxn];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	ll n,a,b;
	cin >> n >> a >> b;
	ll gcd = __gcd(a,b+1); 
	ll maxi = a/gcd*b; 
	bool all=0;
	vector<pll>seg;
	for(int i=0; i<n; i++){
		cin >> l[i] >> r[i];
		if(r[i]-l[i]+1>=maxi)all=1;
		l[i]%=maxi; r[i]%=maxi;
		if(r[i]>=l[i]){
			seg.emplace_back(pll(l[i],r[i]));
		}else{
			seg.emplace_back(pll((ll)0,r[i]));
			seg.emplace_back(pll(l[i],ll(maxi-1)));
		}
	}
	if(all){
		cout << maxi << endl;
		return 0;
	}
	sort(all(seg));
	ll ans = 0;
	ll cur = 0;
	for(int i=0; i<(int)seg.size(); i++){
		ans += max(ll(0),seg[i].se+1-max(seg[i].fi,cur));
		cur = max(seg[i].se+1,cur);
	}
	cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 1280 KB Output is correct
3 Correct 11 ms 1280 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 10 ms 1280 KB Output is correct
17 Correct 60 ms 7272 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 409 ms 35160 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 535 ms 37136 KB Output is correct
3 Correct 536 ms 37324 KB Output is correct
4 Correct 526 ms 37328 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 535 ms 37136 KB Output is correct
3 Correct 536 ms 37324 KB Output is correct
4 Correct 526 ms 37328 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 571 ms 37232 KB Output is correct
7 Correct 523 ms 37264 KB Output is correct
8 Correct 542 ms 37472 KB Output is correct
9 Correct 703 ms 37460 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 535 ms 37136 KB Output is correct
3 Correct 536 ms 37324 KB Output is correct
4 Correct 526 ms 37328 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 55 ms 7404 KB Output is correct
7 Correct 62 ms 7324 KB Output is correct
8 Correct 57 ms 7400 KB Output is correct
9 Correct 66 ms 7276 KB Output is correct
10 Correct 58 ms 7400 KB Output is correct
11 Correct 58 ms 7324 KB Output is correct
12 Correct 57 ms 7400 KB Output is correct
13 Correct 60 ms 7276 KB Output is correct
14 Correct 58 ms 7400 KB Output is correct
15 Correct 61 ms 7404 KB Output is correct
16 Correct 65 ms 7268 KB Output is correct
17 Correct 57 ms 7276 KB Output is correct
18 Correct 519 ms 37184 KB Output is correct
19 Correct 528 ms 37312 KB Output is correct
20 Correct 603 ms 37312 KB Output is correct
21 Correct 63 ms 7276 KB Output is correct
22 Correct 60 ms 7272 KB Output is correct
23 Correct 171 ms 23764 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 58 ms 7276 KB Output is correct
3 Correct 68 ms 7272 KB Output is correct
4 Correct 589 ms 37156 KB Output is correct
5 Correct 60 ms 7276 KB Output is correct
6 Correct 64 ms 7276 KB Output is correct
7 Correct 58 ms 7276 KB Output is correct
8 Correct 63 ms 7276 KB Output is correct
9 Correct 57 ms 7272 KB Output is correct
10 Correct 61 ms 7272 KB Output is correct
11 Correct 62 ms 7272 KB Output is correct
12 Correct 53 ms 7276 KB Output is correct
13 Correct 58 ms 7276 KB Output is correct
14 Correct 590 ms 37184 KB Output is correct
15 Correct 63 ms 7276 KB Output is correct
16 Correct 553 ms 37184 KB Output is correct
17 Correct 542 ms 37272 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 1280 KB Output is correct
3 Correct 11 ms 1280 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 10 ms 1280 KB Output is correct
17 Correct 60 ms 7272 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct