oj.uz

Submission #933152

# Submission time Handle Problem Language Result Execution time Memory
933152 2024-02-25T07:25:56 Z 8pete8 Strange Device (APIO19_strange_device) C++17
65 / 100
 1360 ms 160884 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=1e6,lg=30,inf=2e18+1,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;
int GCD(int x, int y)
{
    if (y == 0) return x;
    return GCD(y, x%y);
}
int li[mxn+10],ri[mxn+10];
int32_t main(){
	fastio
	int n;cin>>n;
	int a,b;cin>>a>>b;
	int k;
	int sum=0;
	for(int i=0;i<n;i++)cin>>li[i]>>ri[i],sum+=ri[i]-li[i]+1;
	k=(GCD(a,b+1));
	int c=k/inf;
	if((double)(ri[n-1]/(a/k))<=double(b))return cout<<sum,0;
	k=a/k;
	k=k*b;
	mp[0]=0;
	mp[k-1]=0;
	//if(k<=0)assert(0);
	for(int i=0;i<n;i++){
		int l=li[i],r=ri[i];
		l=(l%k);
		r=(r%k);
		if(r-l+1>=k)return cout<<k,0;
		mp[l-1]+=0;
		mp[l]+=1;
		if(r+1<k)mp[r+1]-=1;
		mp[r]+=0;
		if(l>r)mp[0]+=1;
	}
	sum=0;
	int ans=0,last=-1;
	for(auto i:mp){
		if(i.f>=k)break;
		sum+=i.s;
		if(sum>0)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%(k) 
	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:55:6: warning: unused variable 'c' [-Wunused-variable]
   55 |  int c=k/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 1 ms 2396 KB Output is correct
2 Correct 7 ms 4188 KB Output is correct
3 Correct 6 ms 4188 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 6 ms 4188 KB Output is correct
17 Correct 59 ms 15300 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 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 1 ms 2396 KB Output is correct
2 Correct 2 ms 2524 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 197 ms 29324 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 612 ms 97728 KB Output is correct
3 Correct 831 ms 160592 KB Output is correct
4 Correct 859 ms 160648 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 612 ms 97728 KB Output is correct
3 Correct 831 ms 160592 KB Output is correct
4 Correct 859 ms 160648 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 812 ms 160508 KB Output is correct
7 Correct 680 ms 98132 KB Output is correct
8 Correct 816 ms 160684 KB Output is correct
9 Correct 1104 ms 160760 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 612 ms 97728 KB Output is correct
3 Correct 831 ms 160592 KB Output is correct
4 Correct 859 ms 160648 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 66 ms 21624 KB Output is correct
7 Correct 63 ms 21664 KB Output is correct
8 Correct 65 ms 21544 KB Output is correct
9 Correct 73 ms 21500 KB Output is correct
10 Correct 65 ms 21572 KB Output is correct
11 Correct 78 ms 21768 KB Output is correct
12 Correct 66 ms 21584 KB Output is correct
13 Correct 77 ms 21528 KB Output is correct
14 Correct 64 ms 21728 KB Output is correct
15 Correct 85 ms 21636 KB Output is correct
16 Correct 98 ms 21736 KB Output is correct
17 Correct 74 ms 21912 KB Output is correct
18 Correct 789 ms 160800 KB Output is correct
19 Correct 959 ms 160748 KB Output is correct
20 Correct 1107 ms 160628 KB Output is correct
21 Correct 67 ms 21584 KB Output is correct
22 Correct 69 ms 21588 KB Output is correct
23 Correct 90 ms 17804 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 78 ms 21444 KB Output is correct
3 Correct 84 ms 21588 KB Output is correct
4 Correct 1036 ms 160672 KB Output is correct
5 Correct 88 ms 21572 KB Output is correct
6 Correct 83 ms 21416 KB Output is correct
7 Correct 88 ms 21596 KB Output is correct
8 Correct 83 ms 21496 KB Output is correct
9 Correct 74 ms 21588 KB Output is correct
10 Correct 74 ms 21716 KB Output is correct
11 Correct 72 ms 21588 KB Output is correct
12 Correct 70 ms 21412 KB Output is correct
13 Correct 79 ms 21628 KB Output is correct
14 Correct 1360 ms 160884 KB Output is correct
15 Correct 67 ms 21548 KB Output is correct
16 Correct 820 ms 160856 KB Output is correct
17 Correct 776 ms 160404 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 7 ms 4188 KB Output is correct
3 Correct 6 ms 4188 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 6 ms 4188 KB Output is correct
17 Correct 59 ms 15300 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Incorrect 1 ms 2396 KB Output isn't correct
21 Halted 0 ms 0 KB -