oj.uz

Submission #933139

# Submission time Handle Problem Language Result Execution time Memory
933139 2024-02-25T06:57:36 Z 8pete8 Strange Device (APIO19_strange_device) C++17
35 / 100
 929 ms 145004 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+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;
int32_t main(){
	fastio
	int n;cin>>n;
	int a,b;cin>>a>>b;
	int k=min((a*(b+1))/gcd(a,b+1),inf);
	if(k!=inf)k=(k/(b+1));
	k=min(inf,k*b);
	mp[0]=0;
	mp[k-1]=0;
	if(k<=0)assert(0);
	for(int i=0;i<n;i++){
		int l,r;cin>>l>>r;
		l=(l%k);
		r=(r%k);
		mp[l-1]+=0;
		mp[l]+=1;
		//if(l>=k||r>=k)assert(0);
		if(r+1<k)mp[r+1]-=1;
		mp[r]+=0;
		if(l>r)mp[0]+=1;
	}
	int sum=0,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 '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 9 ms 1628 KB Output is correct
3 Correct 7 ms 1624 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 516 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 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 7 ms 1940 KB Output is correct
17 Correct 79 ms 8872 KB Output is correct
18 Runtime error 1 ms 600 KB Execution killed with signal 6
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 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 856 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 236 ms 13596 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 654 ms 82376 KB Output is correct
3 Correct 808 ms 145004 KB Output is correct
4 Correct 857 ms 144844 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 654 ms 82376 KB Output is correct
3 Correct 808 ms 145004 KB Output is correct
4 Correct 857 ms 144844 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 785 ms 144916 KB Output is correct
7 Correct 672 ms 82088 KB Output is correct
8 Correct 793 ms 144880 KB Output is correct
9 Correct 861 ms 144704 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 654 ms 82376 KB Output is correct
3 Correct 808 ms 145004 KB Output is correct
4 Correct 857 ms 144844 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 62 ms 15292 KB Output is correct
7 Correct 63 ms 15184 KB Output is correct
8 Correct 65 ms 15296 KB Output is correct
9 Correct 74 ms 15184 KB Output is correct
10 Correct 64 ms 15308 KB Output is correct
11 Correct 64 ms 15184 KB Output is correct
12 Correct 65 ms 15216 KB Output is correct
13 Correct 73 ms 15080 KB Output is correct
14 Correct 71 ms 15220 KB Output is correct
15 Correct 74 ms 15184 KB Output is correct
16 Correct 94 ms 15108 KB Output is correct
17 Correct 71 ms 15184 KB Output is correct
18 Correct 753 ms 144720 KB Output is correct
19 Correct 826 ms 144732 KB Output is correct
20 Correct 903 ms 144640 KB Output is correct
21 Correct 69 ms 15148 KB Output is correct
22 Correct 70 ms 15188 KB Output is correct
23 Correct 83 ms 7248 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 76 ms 15232 KB Output is correct
3 Correct 77 ms 15188 KB Output is correct
4 Correct 852 ms 144876 KB Output is correct
5 Correct 77 ms 15244 KB Output is correct
6 Correct 81 ms 15184 KB Output is correct
7 Correct 77 ms 15048 KB Output is correct
8 Correct 77 ms 15184 KB Output is correct
9 Correct 73 ms 15184 KB Output is correct
10 Correct 68 ms 15116 KB Output is correct
11 Correct 70 ms 15172 KB Output is correct
12 Correct 71 ms 15224 KB Output is correct
13 Correct 74 ms 15184 KB Output is correct
14 Correct 929 ms 144596 KB Output is correct
15 Correct 66 ms 15296 KB Output is correct
16 Correct 772 ms 144612 KB Output is correct
17 Correct 750 ms 144592 KB Output is correct
18 Runtime error 1 ms 604 KB Execution killed with signal 6
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 9 ms 1628 KB Output is correct
3 Correct 7 ms 1624 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 516 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 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 7 ms 1940 KB Output is correct
17 Correct 79 ms 8872 KB Output is correct
18 Runtime error 1 ms 600 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -