oj.uz

Submission #933116

# Submission time Handle Problem Language Result Execution time Memory
933116 2024-02-25T06:22:39 Z 8pete8 Strange Device (APIO19_strange_device) C++17
65 / 100
 1049 ms 144408 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=1e18,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*=b;
	int mx=minf,mn=inf;
	bool yes=false;
	mp[k-1]=0;
	mp[0]=0;
	//cout<<k<<'\n';
	for(int i=0;i<n;i++){
		int l,r;cin>>l>>r;
		//cout<<l<<" "<<r<<'\n';
		if(n==1){
			l%=k,r%=k;
			if(l<r)cout<<r-l+1;
			else cout<<k-l+r;
			return 0;
		}
		if(r-l+1>=k)yes=1;
		else{
			l%=k,r%=k;
			mp[l-1]+=0;
			mp[l]+=1,mp[r+1]-=1;
			mp[r]+=0;
			if(l>r)mp[0]+=1;
		}
	}
	//cout<<'\n';
	if(yes)return cout<<k<<'\n',0;
	int sum=0,ans=0,last=-1;
	for(auto i:mp){
		sum+=i.s;
	//	cout<<i.f<<" "<<sum<<'\n';
		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 'int32_t main()':
strange_device.cpp:48:6: warning: unused variable 'mx' [-Wunused-variable]
   48 |  int mx=minf,mn=inf;
      |      ^~
strange_device.cpp:48:14: warning: unused variable 'mn' [-Wunused-variable]
   48 |  int mx=minf,mn=inf;
      |              ^~
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 2092 KB Output is correct
3 Correct 6 ms 1884 KB Output is correct
4 Correct 0 ms 408 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 348 KB Output is correct
8 Correct 1 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 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 6 ms 1884 KB Output is correct
17 Correct 59 ms 8600 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 679 ms 81752 KB Output is correct
3 Correct 842 ms 144408 KB Output is correct
4 Correct 968 ms 144176 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 679 ms 81752 KB Output is correct
3 Correct 842 ms 144408 KB Output is correct
4 Correct 968 ms 144176 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 820 ms 144164 KB Output is correct
7 Correct 660 ms 81560 KB Output is correct
8 Correct 818 ms 144212 KB Output is correct
9 Correct 1049 ms 144208 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 679 ms 81752 KB Output is correct
3 Correct 842 ms 144408 KB Output is correct
4 Correct 968 ms 144176 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 62 ms 15040 KB Output is correct
7 Correct 66 ms 14932 KB Output is correct
8 Correct 63 ms 14812 KB Output is correct
9 Correct 80 ms 15080 KB Output is correct
10 Correct 61 ms 14908 KB Output is correct
11 Correct 63 ms 14936 KB Output is correct
12 Correct 73 ms 14936 KB Output is correct
13 Correct 81 ms 14932 KB Output is correct
14 Correct 65 ms 15036 KB Output is correct
15 Correct 77 ms 15024 KB Output is correct
16 Correct 75 ms 14896 KB Output is correct
17 Correct 70 ms 14844 KB Output is correct
18 Correct 798 ms 125868 KB Output is correct
19 Correct 885 ms 125504 KB Output is correct
20 Correct 935 ms 125652 KB Output is correct
21 Correct 65 ms 12880 KB Output is correct
22 Correct 81 ms 13004 KB Output is correct
23 Correct 76 ms 348 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 84 ms 12864 KB Output is correct
3 Correct 76 ms 12884 KB Output is correct
4 Correct 921 ms 125640 KB Output is correct
5 Correct 75 ms 12792 KB Output is correct
6 Correct 85 ms 13016 KB Output is correct
7 Correct 80 ms 12868 KB Output is correct
8 Correct 89 ms 12920 KB Output is correct
9 Correct 74 ms 12884 KB Output is correct
10 Correct 65 ms 12884 KB Output is correct
11 Correct 75 ms 12896 KB Output is correct
12 Correct 69 ms 12740 KB Output is correct
13 Correct 81 ms 12884 KB Output is correct
14 Correct 1014 ms 125676 KB Output is correct
15 Correct 63 ms 12880 KB Output is correct
16 Correct 791 ms 125676 KB Output is correct
17 Correct 756 ms 125568 KB Output is correct
18 Correct 1 ms 348 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 2092 KB Output is correct
3 Correct 6 ms 1884 KB Output is correct
4 Correct 0 ms 408 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 348 KB Output is correct
8 Correct 1 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 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 6 ms 1884 KB Output is correct
17 Correct 59 ms 8600 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -