Submission #333140

#	Time	Username	Problem	Language	Result	Execution time	Memory
333140		etaha	Strange Device (APIO19_strange_device)	C++14	10 / 100	994 ms	33412 KiB

strange_device

//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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30