oj.uz

답안 #975519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975519 2024-05-05T11:52:35 Z Batorgil952 이상한 기계 (APIO19_strange_device) C++14
5 / 100
 576 ms 429008 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

const ll N=1e7+7;
struct Node{
	ll l;
	ll r;
	ll vl=-1;
	ll vr=-1;
	ll val=0;
};
Node tree[N];
ll K;

ll GCD(ll x, ll y){
	while(x*y!=0){
		if(x>y) x%=y;
		else y%=x;
	}
	return x+y;
}

void update(ll v, ll ql, ll qr){
//	cout<<v<<" "<<ql<<" "<<qr<<" "<<tree[v].l<<" "<<tree[v].r<<" "<<tree[v].val<<endl;
	if(tree[v].val==tree[v].r-tree[v].l+1){
		return;
	}
	if(qr<tree[v].l && tree[v].r<ql){
		return;
	}
	if(ql<=tree[v].l && tree[v].r<=qr){
		tree[v].val=tree[v].r-tree[v].l+1;
		return;
	}
	ll mid=(tree[v].l+tree[v].r)/2;
	if(qr<=mid){
		if(tree[v].vl==-1){
			K++;
			tree[v].vl=K;
			tree[tree[v].vl].l=tree[v].l;
			tree[tree[v].vl].r=mid;
			update(tree[v].vl, ql, qr);
		}
		else if(tree[tree[v].vl].val!=mid-tree[v].l+1){
			update(tree[v].vl, ql, qr);
		}
	}
	else if(mid+1<=ql){
		if(tree[v].vr==-1){
			K++;
			tree[v].vr=K;
			tree[tree[v].vr].l=mid+1;
			tree[tree[v].vr].r=tree[v].r;
			update(tree[v].vr, ql, qr);
		}
		else if(tree[tree[v].vl].val!=tree[v].r-mid){
			update(tree[v].vr, ql, qr);
		}
	}
	else{
		if(tree[v].vl==-1){
			K++;
			tree[v].vl=K;
			tree[tree[v].vl].l=tree[v].l;
			tree[tree[v].vl].r=mid;
			update(tree[v].vl, ql, qr);
		}
		else if(tree[tree[v].vl].val!=mid-tree[v].l+1){
			update(tree[v].vl, ql, qr);
		}
		if(tree[v].vr==-1){
			K++;
			tree[v].vr=K;
			tree[tree[v].vr].l=mid+1;
			tree[tree[v].vr].r=tree[v].r;
			update(tree[v].vr, ql, qr);
		}
		else if(tree[tree[v].vl].val!=tree[v].r-mid){
			update(tree[v].vr, ql, qr);
		}
	}
	tree[v].val=tree[tree[v].vl].val+tree[tree[v].vr].val;
	
}

ll query(ll v, ll l, ll r){
	return tree[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=1e18+1;
	if(ma/A<B){
		k=ma;
	}
	else{
		k=A*B;
	}
//	cout<<k<<endl;
	
	tree[0].l=0;
	tree[0].r=k-1;
	K=0;
	for(i=1; i<=n; i++){
		scanf("%lld",&l);
		scanf("%lld",&r);
		if(r-l+1>=k) update(0, 0, k-1);
		else{
			if(l%k<=r%k){
				update(0, l%k, r%k);
			}
			else{
				update(0, l%k, k-1);
				update(0, 0, r%k);
			}
		}
	}
	
	printf("%lld\n", query(0, 0, k-1));
	
	return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 391768 KB Output is correct
2 Incorrect 111 ms 392020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 391668 KB Output is correct
2 Correct 106 ms 391760 KB Output is correct
3 Correct 104 ms 391684 KB Output is correct
4 Correct 104 ms 391652 KB Output is correct
5 Correct 104 ms 391652 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 391816 KB Output is correct
2 Incorrect 107 ms 391760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 391652 KB Output is correct
2 Incorrect 576 ms 429008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 391652 KB Output is correct
2 Incorrect 576 ms 429008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 391652 KB Output is correct
2 Incorrect 576 ms 429008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 391800 KB Output is correct
2 Incorrect 161 ms 395428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 391768 KB Output is correct
2 Incorrect 111 ms 392020 KB Output isn't correct
3 Halted 0 ms 0 KB -