oj.uz

Submission #333142

# Submission time Handle Problem Language Result Execution time Memory
333142 2020-12-04T18:57:46 Z etaha Strange Device (APIO19_strange_device) C++14
10 / 100
 922 ms 34236 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>((lint)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 7 ms 1008 KB Output is correct
4 Incorrect 1 ms 364 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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 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 458 ms 33340 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 765 ms 33468 KB Output is correct
3 Incorrect 664 ms 34236 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 364 KB Output is correct
2 Correct 765 ms 33468 KB Output is correct
3 Incorrect 664 ms 34236 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 364 KB Output is correct
2 Correct 765 ms 33468 KB Output is correct
3 Incorrect 664 ms 34236 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 76 ms 5140 KB Output is correct
3 Correct 77 ms 5220 KB Output is correct
4 Correct 922 ms 33340 KB Output is correct
5 Correct 81 ms 5476 KB Output is correct
6 Correct 77 ms 5476 KB Output is correct
7 Correct 79 ms 5476 KB Output is correct
8 Correct 81 ms 5476 KB Output is correct
9 Correct 74 ms 5476 KB Output is correct
10 Correct 82 ms 5476 KB Output is correct
11 Correct 76 ms 5476 KB Output is correct
12 Correct 67 ms 5476 KB Output is correct
13 Correct 82 ms 5476 KB Output is correct
14 Correct 871 ms 34108 KB Output is correct
15 Incorrect 82 ms 5476 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 7 ms 1008 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -