oj.uz

Submission #933133

# Submission time Handle Problem Language Result Execution time Memory
933133 2024-02-25T06:42:54 Z 8pete8 Strange Device (APIO19_strange_device) C++17
65 / 100
 1000 ms 125808 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
const int mod=1e9+7,mxn=2e5,lg=30,inf=2e18,minf=-1e18,Mxn=2e6,root=700;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}	 
map<int,int>mp;
int32_t main(){
	fastio
	int n;cin>>n;
	int a,b;cin>>a>>b;
	int k=(a*(b+1))/gcd(a,b+1);
	k=(k/(b+1));
	k=min(inf,k*b);
	mp[k-1]=0;
	mp[0]=0;
	bool yes=false;
	for(int i=0;i<n;i++){
		int l,r;cin>>l>>r;
//		if(r-l+1>k)yes=true;
		l%=k,r%=k;
		mp[l-1]+=0;
		mp[l]+=1,mp[r+1]-=1;
		mp[r]+=0;
		if(l>r)mp[0]+=1;
	}
	if(yes)return cout<<k<<'\n',0;
	int sum=0,ans=0,last=-1;
	for(auto i:mp){
		//if(i.f>=k)break;
		sum+=i.s;
		if(sum)ans+=i.f-last;
		last=i.f;
	}
	cout<<ans;
	/*
	observation:
	y=t mod b
	x=(t+(k*b)+[t/b]+k)%a
	x=t+t[t/b]%a
	(k*(b+1))%a==0
	case 1 : (b+1)%a==0 -> k can be anything -> if y equal is equal ->k==1
	case 2 : k%a==0 -> k=g(a) -> k is a multiple of a ->val jump every k*b
	*|k=lcm(a,b+1)/(b+1)|*
	considering 1 range l,r
	first occurance of y=t mod b
 
	if r-l+1>k then it will cover all k
 
	block of b (range where all y value will be distinct)
	|		|		|		|
	if(k==2)
	block will be (range where all (x,y) value will be distinct)
	|				|				|
	
	find ways to count x%(a*b) or x%b
	in a given set of range l,r
	l,r will cover a range of block
	can use prefix sum??
	*/
}

Compilation message

strange_device.cpp: In function 'void setIO(std::string)':
strange_device.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 7 ms 1780 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 63 ms 6912 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 175 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 609 ms 63064 KB Output is correct
3 Correct 816 ms 125716 KB Output is correct
4 Correct 914 ms 125696 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 609 ms 63064 KB Output is correct
3 Correct 816 ms 125716 KB Output is correct
4 Correct 914 ms 125696 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 794 ms 125556 KB Output is correct
7 Correct 669 ms 63116 KB Output is correct
8 Correct 826 ms 125716 KB Output is correct
9 Correct 901 ms 125448 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 609 ms 63064 KB Output is correct
3 Correct 816 ms 125716 KB Output is correct
4 Correct 914 ms 125696 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 62 ms 12892 KB Output is correct
7 Correct 64 ms 12888 KB Output is correct
8 Correct 62 ms 12764 KB Output is correct
9 Correct 84 ms 12980 KB Output is correct
10 Correct 60 ms 12944 KB Output is correct
11 Correct 72 ms 12884 KB Output is correct
12 Correct 64 ms 12880 KB Output is correct
13 Correct 93 ms 12884 KB Output is correct
14 Correct 67 ms 12784 KB Output is correct
15 Correct 82 ms 12884 KB Output is correct
16 Correct 76 ms 12884 KB Output is correct
17 Correct 70 ms 12880 KB Output is correct
18 Correct 773 ms 125700 KB Output is correct
19 Correct 925 ms 125632 KB Output is correct
20 Correct 882 ms 125628 KB Output is correct
21 Correct 67 ms 12884 KB Output is correct
22 Correct 71 ms 12860 KB Output is correct
23 Correct 78 ms 432 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 74 ms 12984 KB Output is correct
3 Correct 75 ms 12816 KB Output is correct
4 Correct 869 ms 125716 KB Output is correct
5 Correct 74 ms 12924 KB Output is correct
6 Correct 82 ms 12796 KB Output is correct
7 Correct 78 ms 12880 KB Output is correct
8 Correct 73 ms 12884 KB Output is correct
9 Correct 70 ms 12876 KB Output is correct
10 Correct 66 ms 12880 KB Output is correct
11 Correct 78 ms 13140 KB Output is correct
12 Correct 67 ms 12880 KB Output is correct
13 Correct 72 ms 12888 KB Output is correct
14 Correct 1000 ms 125808 KB Output is correct
15 Correct 63 ms 12880 KB Output is correct
16 Correct 738 ms 125524 KB Output is correct
17 Correct 757 ms 125676 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 7 ms 1780 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 63 ms 6912 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -