oj.uz

Submission #933127

# Submission time Handle Problem Language Result Execution time Memory
933127 2024-02-25T06:36:10 Z 8pete8 Strange Device (APIO19_strange_device) C++17
65 / 100
 1049 ms 144868 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;
	//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<<'\n';
			else cout<<k-l+r+1<<'\n';
			//return 0;
		}*/
		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';
	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 '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 344 KB Output is correct
2 Correct 8 ms 1884 KB Output is correct
3 Correct 7 ms 1944 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 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 604 KB Output is correct
14 Correct 0 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 65 ms 9056 KB Output is correct
18 Correct 0 ms 348 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 200 ms 13284 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 626 ms 81848 KB Output is correct
3 Correct 798 ms 144528 KB Output is correct
4 Correct 855 ms 144620 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 626 ms 81848 KB Output is correct
3 Correct 798 ms 144528 KB Output is correct
4 Correct 855 ms 144620 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 784 ms 144460 KB Output is correct
7 Correct 664 ms 81836 KB Output is correct
8 Correct 836 ms 144832 KB Output is correct
9 Correct 1049 ms 144868 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 626 ms 81848 KB Output is correct
3 Correct 798 ms 144528 KB Output is correct
4 Correct 855 ms 144620 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 76 ms 15192 KB Output is correct
7 Correct 62 ms 15188 KB Output is correct
8 Correct 78 ms 15188 KB Output is correct
9 Correct 77 ms 15184 KB Output is correct
10 Correct 62 ms 15188 KB Output is correct
11 Correct 62 ms 15188 KB Output is correct
12 Correct 66 ms 15288 KB Output is correct
13 Correct 72 ms 15188 KB Output is correct
14 Correct 71 ms 15312 KB Output is correct
15 Correct 74 ms 15184 KB Output is correct
16 Correct 75 ms 15088 KB Output is correct
17 Correct 76 ms 15192 KB Output is correct
18 Correct 766 ms 144668 KB Output is correct
19 Correct 883 ms 144164 KB Output is correct
20 Correct 938 ms 144308 KB Output is correct
21 Correct 69 ms 15044 KB Output is correct
22 Correct 69 ms 14788 KB Output is correct
23 Correct 80 ms 6924 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 77 ms 14800 KB Output is correct
3 Correct 83 ms 15120 KB Output is correct
4 Correct 897 ms 144572 KB Output is correct
5 Correct 88 ms 14848 KB Output is correct
6 Correct 88 ms 14984 KB Output is correct
7 Correct 78 ms 14928 KB Output is correct
8 Correct 87 ms 14956 KB Output is correct
9 Correct 71 ms 14896 KB Output is correct
10 Correct 69 ms 14984 KB Output is correct
11 Correct 75 ms 14928 KB Output is correct
12 Correct 69 ms 14928 KB Output is correct
13 Correct 82 ms 14928 KB Output is correct
14 Correct 943 ms 144396 KB Output is correct
15 Correct 66 ms 14908 KB Output is correct
16 Correct 751 ms 144484 KB Output is correct
17 Correct 795 ms 144168 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1884 KB Output is correct
3 Correct 7 ms 1944 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 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 604 KB Output is correct
14 Correct 0 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 65 ms 9056 KB Output is correct
18 Correct 0 ms 348 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 -