oj.uz

Submission #933115

# Submission time Handle Problem Language Result Execution time Memory
933115 2024-02-25T06:20:10 Z 8pete8 Strange Device (APIO19_strange_device) C++17
35 / 100
 1075 ms 163072 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(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 2052 KB Output is correct
3 Correct 6 ms 1884 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 6 ms 1884 KB Output is correct
17 Correct 60 ms 10464 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 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 488 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 201 ms 25524 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 611 ms 100160 KB Output is correct
3 Correct 852 ms 162828 KB Output is correct
4 Correct 903 ms 163072 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 611 ms 100160 KB Output is correct
3 Correct 852 ms 162828 KB Output is correct
4 Correct 903 ms 163072 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 798 ms 162608 KB Output is correct
7 Correct 667 ms 100384 KB Output is correct
8 Correct 819 ms 162824 KB Output is correct
9 Correct 1075 ms 162972 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 611 ms 100160 KB Output is correct
3 Correct 852 ms 162828 KB Output is correct
4 Correct 903 ms 163072 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 62 ms 16568 KB Output is correct
7 Correct 64 ms 16468 KB Output is correct
8 Correct 65 ms 16532 KB Output is correct
9 Correct 73 ms 16468 KB Output is correct
10 Correct 63 ms 16720 KB Output is correct
11 Correct 69 ms 16696 KB Output is correct
12 Correct 67 ms 16464 KB Output is correct
13 Correct 73 ms 16464 KB Output is correct
14 Correct 63 ms 16472 KB Output is correct
15 Correct 90 ms 16468 KB Output is correct
16 Correct 87 ms 16488 KB Output is correct
17 Correct 70 ms 16468 KB Output is correct
18 Correct 801 ms 162648 KB Output is correct
19 Correct 841 ms 162828 KB Output is correct
20 Correct 860 ms 162592 KB Output is correct
21 Correct 68 ms 16604 KB Output is correct
22 Correct 70 ms 16464 KB Output is correct
23 Correct 80 ms 12984 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 75 ms 16680 KB Output is correct
3 Correct 76 ms 16580 KB Output is correct
4 Correct 842 ms 162824 KB Output is correct
5 Correct 79 ms 16688 KB Output is correct
6 Correct 78 ms 16468 KB Output is correct
7 Correct 86 ms 16768 KB Output is correct
8 Correct 74 ms 16464 KB Output is correct
9 Correct 72 ms 16464 KB Output is correct
10 Correct 68 ms 16464 KB Output is correct
11 Correct 72 ms 16456 KB Output is correct
12 Correct 71 ms 16464 KB Output is correct
13 Correct 74 ms 16716 KB Output is correct
14 Correct 1033 ms 162636 KB Output is correct
15 Correct 63 ms 16516 KB Output is correct
16 Correct 777 ms 163024 KB Output is correct
17 Correct 760 ms 162840 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 2052 KB Output is correct
3 Correct 6 ms 1884 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 6 ms 1884 KB Output is correct
17 Correct 60 ms 10464 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -