oj.uz

Submission #977091

# Submission time Handle Problem Language Result Execution time Memory
977091 2024-05-07T11:25:14 Z Batorgil952 Strange Device (APIO19_strange_device) C++14
20 / 100
 955 ms 524288 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
 
using namespace std;
 
struct Node{
	ll val, le, ri;
	bool al, ar;
	Node *Left;
	Node *Right;
	Node(ll l, ll r){
		le=l;
		ri=r;
		Left=nullptr;
		Right=nullptr;
		al=0;
		ar=0;
		val=0;
	}
};
 
ll GCD(ll x, ll y){
	while(x*y!=0){
		if(x>y) x%=y;
		else y%=x;
	}
	return x+y;
}
 
void update(Node *v, ll ql, ll qr){
	if(v->val==v->ri-v->le+1){
		return;
	}
	if(qr<v->le && v->ri<ql){
		return;
	}
	if(ql<=v->le && v->ri<=qr){
		v->val=v->ri-v->le+1;
		return;
	}
	ll mid=(v->le+v->ri)/2;
	if(qr<=mid){
		if(!v->al){
			if(v->Left==nullptr){
				v->Left=new Node(v->le, mid);
				update(v->Left, ql, qr);
			}
			else if(v->Left->val!=mid-v->le+1){
				update(v->Left, ql, qr);
			}
		}
	}
	else if(mid+1<=ql){
		if(!v->ar){
			if(v->Right==nullptr){
				v->Right=new Node(mid+1, v->ri);
				update(v->Right, ql, qr);
			}
			else if(v->Right->val!=v->ri-mid){
				update(v->Right, ql, qr);
			}
		}
	}
	else if(ql<=v->le && mid<=qr){
		v->al=1;
		if(!v->ar){
			if(v->Right==nullptr){
				v->Right=new Node(mid+1, v->ri);
				update(v->Right, ql, qr);
			}
			else if(v->Right->val!=v->ri-mid){
				update(v->Right, ql, qr);
			}
		}
	}
	else if(ql<=mid+1 && v->ri<=qr){
		v->ar=1;
		if(!v->al){
			if(v->Left==nullptr){
				v->Left=new Node(v->le, mid);
				update(v->Left, ql, qr);
			}
			else if(v->Left->val!=mid-v->le+1){
				update(v->Left, ql, qr);
			}
		}
	}
	else{
		if(v->Left==nullptr){
			v->Left=new Node(v->le, mid);
			update(v->Left, ql, qr);
		}
		else if(v->Left->val!=mid-v->le+1){
			update(v->Left, ql, qr);
		}
		if(v->Right==nullptr){
			v->Right=new Node(mid+1, v->ri);
			update(v->Right, ql, qr);
		}
		else if(v->Right->val!=v->ri-mid){
			update(v->Right, ql, qr);
		}
	}
	v->val=0;
	if(v->al){
		v->val+=(mid-v->le+1);
	}
	else{
		if(v->Left!=nullptr) v->val+=v->Left->val;
	}
	if(v->ar){
		v->val+=(v->ri-mid);
	}
	else{
		if(v->Right!=nullptr) v->val+=v->Right->val;
	}
}
 
ll query(Node *v, ll l, ll r){
	return v->val;
}
 
 
int main(){
	ll n, i, A, B, l, r, k, m, ma;
	
	scanf("%lld",&n);
	scanf("%lld",&A);
	scanf("%lld",&B);
	
	m=GCD(B+1, A);
	A/=m;
	ma=1000000000000000002;
	if(ma/A<B){
		k=ma;
	}
	else{
		k=A*B;
	}
//	cout<<k<<endl;
	
	Node *root = new Node(0, k-1);
	for(i=1; i<=n; i++){
		scanf("%lld",&l);
		scanf("%lld",&r);
		if(r-l+1>=k) update(root, 0, k-1);
		else{
			if(l%k<=r%k){
				update(root, l%k, r%k);
			}
			else{
				update(root, l%k, k-1);
				update(root, 0, r%k);
			}
		}
	}
	
	printf("%lld\n", query(root, 0, k-1));
	
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%lld",&A);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  scanf("%lld",&B);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |   scanf("%lld",&l);
      |   ~~~~~^~~~~~~~~~~
strange_device.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%lld",&r);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 3932 KB Output is correct
3 Correct 9 ms 4564 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 1 ms 348 KB Output is correct
8 Correct 0 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 7 ms 3672 KB Output is correct
17 Correct 51 ms 13176 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

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 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 275 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 530 ms 125524 KB Output is correct
3 Runtime error 955 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 530 ms 125524 KB Output is correct
3 Runtime error 955 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 530 ms 125524 KB Output is correct
3 Runtime error 955 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 98 ms 54320 KB Output is correct
3 Correct 160 ms 111440 KB Output is correct
4 Runtime error 724 ms 524288 KB Execution killed with signal 9
5 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 3932 KB Output is correct
3 Correct 9 ms 4564 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 1 ms 348 KB Output is correct
8 Correct 0 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 7 ms 3672 KB Output is correct
17 Correct 51 ms 13176 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 275 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 530 ms 125524 KB Output is correct
31 Runtime error 955 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -