oj.uz

Submission #169000

# Submission time Handle Problem Language Result Execution time Memory
169000 2019-12-17T13:01:31 Z kshitij_sodani Strange Device (APIO19_strange_device) C++17
5 / 100
 693 ms 70076 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
typedef 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 cc=aa*bb;
			for(llo i=0;i<n;i++){
				it[i].b%=cc;
				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;
						st=tt[i].a;
						end=tt[i].b;
					}
				}
			}
			tot+=end-st+1;
			cout<<tot<<endl;
		
	}

}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo i=0;i<tt.size();i++){
               ~^~~~~~~~~~
strange_device.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(llo i=0;i<tt.size();i++){
                ~^~~~~~~~~~
strange_device.cpp:99:12: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
    tot+=end-st+1;
         ~~~^~~
strange_device.cpp:99:12: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
strange_device.cpp:62:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   tot+=end-st+1;
        ~~~^~~
strange_device.cpp:62:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 9 ms 1272 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 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 464 ms 57856 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 626 ms 70076 KB Output is correct
3 Incorrect 638 ms 69812 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 626 ms 70076 KB Output is correct
3 Incorrect 638 ms 69812 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 626 ms 70076 KB Output is correct
3 Incorrect 638 ms 69812 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 67 ms 7876 KB Output is correct
3 Correct 67 ms 7856 KB Output is correct
4 Correct 693 ms 69808 KB Output is correct
5 Correct 68 ms 7920 KB Output is correct
6 Correct 71 ms 7816 KB Output is correct
7 Correct 68 ms 7856 KB Output is correct
8 Correct 68 ms 7788 KB Output is correct
9 Correct 67 ms 7856 KB Output is correct
10 Correct 67 ms 7792 KB Output is correct
11 Correct 68 ms 7892 KB Output is correct
12 Correct 61 ms 7912 KB Output is correct
13 Correct 67 ms 7840 KB Output is correct
14 Correct 675 ms 69804 KB Output is correct
15 Incorrect 69 ms 7920 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 504 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 9 ms 1272 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -