oj.uz

Submission #333140

# Submission time Handle Problem Language Result Execution time Memory
333140 2020-12-04T18:44:54 Z etaha Strange Device (APIO19_strange_device) C++14
10 / 100
 994 ms 33412 KB 
//debug icin gdb kullanmayi dene
#include<bits/stdc++.h>
using namespace std;
#define mods 1000000007
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<lint,lint> 
#define piii pair<lint,pair<lint,lint> > 
#define inf LLONG_MAX-7
typedef long long int lint;
typedef unsigned long long int ulint;
lint fastpow(lint tab,lint us){
	if(tab==0) return 0;
	if(tab==1) return 1;
	if(us==0) return 1;
	if(us==1) return tab%mods;
	tab%=mods;
	if(us%2==1) return tab*fastpow(tab,us-1)%mods;
	lint a=fastpow(tab,us/2)%mods;
	return a*a%mods;
}
lint t=1,n,m,a,b;
vector<pii> s;
bool comp(pii p1,pii p2){
	if(p1.st==p2.st) return p1.nd>p2.nd;
	return p1.st<p2.st;
}
void ini(lint l,lint r){
	lint i;
	s.pb(mp(l,1));
	s.pb(mp(r,-1));
}
void solve(){
	lint i,l,r,j,k;
	cin>>n>>a>>b;
	if(a>(1e18)/b) m=1e18+5;
	else m=a*b;
	for(i=0;i<n;i++){
		cin>>l>>r;
		if(r-l+1>=m){cout<<m<<endl; return;}
		if((l/m)!=(r/m)){
			ini(0,r%m);
			ini(l%m,m-1);
		}
		else ini(l%m,r%m);
	}
	sort(s.begin(),s.end(),comp);
	lint cev=1,mev=1;
	l=-1;
	for(i=1;i<s.size();i++){
//		cout<<s[i].st<<" "<<s[i].nd<<endl;
		if(mev==0){
			cev++;
		}else cev+=(s[i].st-s[i-1].st);
		mev+=s[i].nd;
	}
	cout<<cev<<endl;
	return;
}

int main(){
//	freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//	cin>>t;
	while(t--) solve();
	return 0;
}

Compilation message

strange_device.cpp: In function 'void ini(lint, lint)':
strange_device.cpp:31:7: warning: unused variable 'i' [-Wunused-variable]
   31 |  lint i;
      |       ^
strange_device.cpp: In function 'void solve()':
strange_device.cpp:52:11: warning: comparison of integer expressions of different signedness: 'lint' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(i=1;i<s.size();i++){
      |          ~^~~~~~~~~
strange_device.cpp:36:13: warning: unused variable 'j' [-Wunused-variable]
   36 |  lint i,l,r,j,k;
      |             ^
strange_device.cpp:36:15: warning: unused variable 'k' [-Wunused-variable]
   36 |  lint i,l,r,j,k;
      |               ^

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 459 ms 33412 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 746 ms 33340 KB Output is correct
3 Incorrect 681 ms 33340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 746 ms 33340 KB Output is correct
3 Incorrect 681 ms 33340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 746 ms 33340 KB Output is correct
3 Incorrect 681 ms 33340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 78 ms 4580 KB Output is correct
3 Correct 82 ms 4580 KB Output is correct
4 Correct 994 ms 33380 KB Output is correct
5 Correct 80 ms 4580 KB Output is correct
6 Correct 80 ms 4580 KB Output is correct
7 Correct 81 ms 4580 KB Output is correct
8 Correct 85 ms 4600 KB Output is correct
9 Correct 92 ms 4580 KB Output is correct
10 Correct 89 ms 4580 KB Output is correct
11 Correct 81 ms 4580 KB Output is correct
12 Correct 69 ms 4580 KB Output is correct
13 Correct 87 ms 4580 KB Output is correct
14 Correct 923 ms 33340 KB Output is correct
15 Incorrect 85 ms 4580 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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