Submission #169008

#	Time	Username	Problem	Language	Result	Execution time	Memory
169008		kshitij_sodani	Strange Device (APIO19_strange_device)	C++17	5 / 100	678 ms	33976 KiB

strange_device

#include <iostream>
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
typedef   unsigned long long int llo;
#define pb push_back

#define a first
#define b second

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
llo inf=10000000000000000000;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,aa,bb;
	cin>>n>>aa>>bb;
	pair<llo,llo> it[n];
	for(llo i=0;i<n;i++){
		cin>>it[i].a>>it[i].b;
	}
	if((bb+1)%aa==0){
		
		vector<pair<llo,llo>> tt;
		for(llo i=0;i<n;i++){
			it[i].b%=bb;
			it[i].a%=bb;
			if(it[i].a<=it[i].b){
				tt.pb(make_pair(it[i].a,it[i].b));
			}
			else{
				tt.pb(make_pair(it[i].a,aa-1));
				tt.pb(make_pair(0,it[i].b));
			}

		}
		sort(tt.begin(),tt.end());
		llo tot=0;
		llo st,end;
		for(llo i=0;i<tt.size();i++){
			if(i==0){
				st=tt[i].a;
				end=tt[i].b;
			}
			else{
				if(tt[i].a<=end){
					end=max(end,tt[i].b);
				}
				else{
					tot+=end-st+1;
					st=tt[i].a;
					end=tt[i].b;
				}
			}
		}
		tot+=end-st+1;
		cout<<tot<<endl;
	}
	else{

			vector<pair<llo,llo>> tt;
			llo num[2];
			num[0]=0;
			num[1]=0;
			//llo co=0;
			llo aaa;
			llo aab;

			llo cc=aa*bb;
		//	int co=aa;
			aaa=aa%(1000000000);
			aab=(aa-aaa)/(1000000000);

			llo bba;
			llo bbb;
			bba=bb%(1000000000);
			bbb=(bb-bba)/(1000000000);
			num[0]+=aaa*bba;

			llo ccc=aaa*bbb;
			ccc=(ccc%1000000000)*(1000000000);
			num[0]+=ccc%1000000000;
			num[1]+=ccc/1000000000;

			ccc=aab*bba;
			ccc=(ccc%1000000000)*(1000000000);
			num[0]+=ccc%1000000000;
			num[1]+=ccc/1000000000;

			llo x=num[0]/1000000000000000000;

			num[0]%=1000000000000000000;
			num[1]+=x;
			num[1]+=bbb*aab;
			llo co=0;
			llo ac=aa;
			while(ac){
				ac/=10;
				co++;
			}
			llo bc=bb;
			while(bc){
				bc/=10;
				co++;
			}
		//	cout<<"done";
			for(llo i=0;i<n;i++){
				if(co<=19){
					it[i].b%=aa*bb;
				}
				if(co<=19){
					it[i].a%=aa*bb;
				}
			//	it[i].b%=bb;

				
			//	it[i].a%=bb;
				//it[i].a%=cc;
				if(it[i].a<=it[i].b){
					tt.pb(make_pair(it[i].a,it[i].b));
				}
				else{
					tt.pb(make_pair(it[i].a,inf));
					tt.pb(make_pair(0,it[i].b));
				}

			}
			sort(tt.begin(),tt.end());
			llo tot[2];
			tot[0]=0;
			tot[1]=0;
			llo st,end;
			for(llo i=0;i<tt.size();i++){
				if(i==0){
					st=tt[i].a;
					end=tt[i].b;
				}
				else{
					if(tt[i].a<=end){
						end=max(end,tt[i].b);
					}
					else{
						if(end!=inf){
							tot[0]+=end-st+1;
						}
						else{
							tot[0]+=num[0];
							tot[1]+=num[1];
							if(tot[0]>=st){

								tot[0]-=st;
							}
							else{
								st-=tot[0];

								tot[0]=0;
								tot[1]-=1;
								tot[0]+=(1000000000000000000-st);
								st/=1000000000;
								tot[1]-=st;
							}
							x=tot[0]/1000000000000000000;

							tot[0]%=1000000000000000000;
							tot[1]+=x;
						}
						//tot+=end-st+1;
						st=tt[i].a;
						end=tt[i].b;
					//	cout<<tot[1]<<" "<<tot[0]<<endl;
					}

				}
			}
		//	cout<<aaa<<" "<<aab<<" "<<bba<<" "<<bbb<<endl;
		//	cout<<num[1]<<" "<<num[0]<<endl;
			if(end!=inf){
				tot[0]+=end-st+1;
			}
			else{
				tot[0]+=num[0];
				tot[1]+=num[1];
				if(tot[0]>=st){

					tot[0]-=st;
				}
				else{
					st-=tot[0];

					tot[0]=0;
					tot[1]-=1;
					tot[0]+=(1000000000000000000-st);
					st/=1000000000;
					tot[1]-=st;
				}
				x=tot[0]/1000000000000000000;

				tot[0]%=1000000000000000000;
				tot[1]+=x;
			}
		//	cout<<tot[1]<<" "<<tot[0]<<endl;
			x=tot[0]/1000000000000000000;

			tot[0]%=1000000000000000000;
			tot[1]+=x;
			if(tot[1]!=0){
				cout<<tot[1];
				ac=tot[0];
				co=0;
				while(ac){
					ac/=10;
					co++;
				}
				for(int i=0;i<co;i++){
					cout<<0;
				}
			}
			cout<<tot[0];
			cout<<endl;
		
	}

}

Compilation message (stderr)

strange_device.cpp:18:9: warning: integer constant is so large that it is unsigned
 llo inf=10000000000000000000;
         ^~~~~~~~~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:221:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<co;i++){
                 ~^~~
strange_device.cpp:76:8: warning: unused variable 'cc' [-Wunused-variable]
    llo cc=aa*bb;
        ^~
strange_device.cpp:139:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
    llo st,end;
           ^~~
strange_device.cpp:195:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
      st-=tot[0];
      ~~^~~~~~~~
strange_device.cpp:46:10: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   llo st,end;
          ^~~
strange_device.cpp:63:6: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   tot+=end-st+1;
   ~~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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