oj.uz

Submission #169012

# Submission time Handle Problem Language Result Execution time Memory
169012 2019-12-17T14:46:49 Z kshitij_sodani Strange Device (APIO19_strange_device) C++17
5 / 100
 677 ms 34388 KB 
#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>

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,bb-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>0){
				ac/=10;
				co+=1;
			}
			llo bc=bb;
			while(bc>0){
				bc/=10;
				co+=1;
			}
			llo cc;
		//	cout<<co<<endl;
			if(co<=(llo)19){
				cc=aa*bb;
			}
		//	cout<<cc<<endl;
		//	cout<<"done";
			for(llo i=0;i<n;i++){
				if(co<=19){
					it[i].b%=cc;
				}
				if(co<=19){
					it[i].a%=cc;
				}
			//	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,cc-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;
						//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;
			tot+=end-st+1;
			cout<<tot;
			cout<<endl;
		
	}

}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:144:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
    llo st,end;
           ^~~
strange_device.cpp:166:7: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
    tot+=end-st+1;
    ~~~^~~~~~~~~~
strange_device.cpp:125:13: warning: 'cc' may be used uninitialized in this function [-Wmaybe-uninitialized]
      it[i].a%=cc;
      ~~~~~~~^~~~
strange_device.cpp:45:10: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   llo st,end;
          ^~~
strange_device.cpp:62:6: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   tot+=end-st+1;
   ~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 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 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 457 ms 33620 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 605 ms 33712 KB Output is correct
3 Incorrect 619 ms 33748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 605 ms 33712 KB Output is correct
3 Incorrect 619 ms 33748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 605 ms 33712 KB Output is correct
3 Incorrect 619 ms 33748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 66 ms 6156 KB Output is correct
3 Correct 66 ms 4240 KB Output is correct
4 Correct 677 ms 33452 KB Output is correct
5 Correct 66 ms 6128 KB Output is correct
6 Correct 67 ms 6128 KB Output is correct
7 Correct 66 ms 5616 KB Output is correct
8 Correct 67 ms 6140 KB Output is correct
9 Correct 65 ms 5232 KB Output is correct
10 Correct 66 ms 6016 KB Output is correct
11 Correct 66 ms 4972 KB Output is correct
12 Correct 59 ms 6100 KB Output is correct
13 Correct 66 ms 6044 KB Output is correct
14 Correct 656 ms 34388 KB Output is correct
15 Incorrect 67 ms 6000 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -