oj.uz

Submission #169010

# Submission time Handle Problem Language Result Execution time Memory
169010 2019-12-17T14:31:53 Z kshitij_sodani Strange Device (APIO19_strange_device) C++17
5 / 100
 676 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>
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 cc=aa*bb;
			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%=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: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:139:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
    llo st,end;
           ^~~
strange_device.cpp:161:7: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
    tot+=end-st+1;
    ~~~^~~~~~~~~~
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.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 376 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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 454 ms 33476 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 612 ms 33748 KB Output is correct
3 Incorrect 612 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 612 ms 33748 KB Output is correct
3 Incorrect 612 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 612 ms 33748 KB Output is correct
3 Incorrect 612 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 6256 KB Output is correct
3 Correct 66 ms 4204 KB Output is correct
4 Correct 676 ms 33244 KB Output is correct
5 Correct 66 ms 6252 KB Output is correct
6 Correct 67 ms 6512 KB Output is correct
7 Correct 67 ms 6308 KB Output is correct
8 Correct 68 ms 6256 KB Output is correct
9 Correct 65 ms 5488 KB Output is correct
10 Correct 66 ms 6128 KB Output is correct
11 Correct 67 ms 5224 KB Output is correct
12 Correct 60 ms 6256 KB Output is correct
13 Correct 67 ms 7788 KB Output is correct
14 Correct 657 ms 34388 KB Output is correct
15 Incorrect 68 ms 7788 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 376 KB Output isn't correct
5 Halted 0 ms 0 KB -