oj.uz

Submission #335113

# Submission time Handle Problem Language Result Execution time Memory
335113 2020-12-11T07:30:10 Z CSQ31 Strange Device (APIO19_strange_device) C++14
65 / 100
 527 ms 17060 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
int main()
{
  owo
	ll n,a,b;
	cin>>n>>a>>b;
	ll v = (INF+b-1)/b;
	v = (v+gcd(a,b+1)-1)/gcd(a,b+1);
	ll C = a>v?INF+1:((a/gcd(a,b+1))*b);
   // cout<<C<<'\n';
	vector<PII>s;
	for(int i=0;i<n;i++){
		ll l,r;
		cin>>l>>r;
		l%=C;
		r%=C;
		if(r >= l){
			s.pb({l,r});
		}else{
			s.pb({l,C-1});
			s.pb({0,r});
		}
	}
	sort(all(s));
	ll ans = 0;
	ll lf = 0;
	ll rg = -1;
	for(int i=0;i<sz(s);i++){
		//cout<<s[i].fi<<" "<<s[i].se<<'\n';
		if(s[i].fi > rg){
			ans+=rg-lf+1;
			lf = s[i].fi;
			rg = s[i].se;
			if(i == sz(s)-1)ans+=rg-lf+1;
		}else{
			rg = max(rg,s[i].se);
			if(i == sz(s)-1)ans+=rg-lf+1;
		}
		//cout<<ans<<'\n';
	}
	cout<<ans<<'\n';
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 48 ms 2536 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 333 ms 16848 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 451 ms 16940 KB Output is correct
3 Correct 446 ms 16996 KB Output is correct
4 Correct 429 ms 16848 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 451 ms 16940 KB Output is correct
3 Correct 446 ms 16996 KB Output is correct
4 Correct 429 ms 16848 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 442 ms 17020 KB Output is correct
7 Correct 444 ms 16848 KB Output is correct
8 Correct 441 ms 16976 KB Output is correct
9 Correct 486 ms 16848 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 451 ms 16940 KB Output is correct
3 Correct 446 ms 16996 KB Output is correct
4 Correct 429 ms 16848 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 43 ms 2536 KB Output is correct
7 Correct 47 ms 2568 KB Output is correct
8 Correct 47 ms 2664 KB Output is correct
9 Correct 44 ms 2536 KB Output is correct
10 Correct 43 ms 2536 KB Output is correct
11 Correct 45 ms 2536 KB Output is correct
12 Correct 43 ms 2536 KB Output is correct
13 Correct 46 ms 2536 KB Output is correct
14 Correct 43 ms 2536 KB Output is correct
15 Correct 47 ms 2536 KB Output is correct
16 Correct 48 ms 2536 KB Output is correct
17 Correct 43 ms 2536 KB Output is correct
18 Correct 450 ms 16964 KB Output is correct
19 Correct 449 ms 17060 KB Output is correct
20 Correct 494 ms 16976 KB Output is correct
21 Correct 47 ms 2536 KB Output is correct
22 Correct 41 ms 2536 KB Output is correct
23 Correct 137 ms 8668 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 50 ms 2536 KB Output is correct
3 Correct 48 ms 2536 KB Output is correct
4 Correct 527 ms 16976 KB Output is correct
5 Correct 48 ms 2536 KB Output is correct
6 Correct 46 ms 2536 KB Output is correct
7 Correct 48 ms 2536 KB Output is correct
8 Correct 49 ms 2536 KB Output is correct
9 Correct 46 ms 2536 KB Output is correct
10 Correct 47 ms 2536 KB Output is correct
11 Correct 48 ms 2536 KB Output is correct
12 Correct 41 ms 2536 KB Output is correct
13 Correct 46 ms 2536 KB Output is correct
14 Correct 488 ms 16976 KB Output is correct
15 Correct 46 ms 2536 KB Output is correct
16 Correct 440 ms 16848 KB Output is correct
17 Correct 444 ms 16848 KB Output is correct
18 Correct 1 ms 492 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 48 ms 2536 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -