oj.uz

답안 #977001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977001 2024-05-07T10:15:17 Z dubabuba 이상한 기계 (APIO19_strange_device) C++14
5 / 100
 1091 ms 52656 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long i64;
typedef pair<i64, i64> pii;
#define ff first
#define ss second
#define MP make_pair
 
struct tree {
	i64 tl, tr, sum;
	tree *lc, *rc;
	bool lazy;
 
	tree(i64 l, i64 r) {
		tl = l;
		tr = r;
		sum = 0;
		lazy = 0;
		lc = NULL;
		rc = NULL;
	}
 
	void upt(i64 l, i64 r) {
		if(lazy) return;
		if(tl == l && r == tr) {
			sum = r - l + 1;
			lazy = 1;
			return;
		}
 
		i64 tm = (tl + tr) / 2;
		if(lc == NULL) lc = new tree(tl, tm);
		if(rc == NULL) rc = new tree(tm + 1, tr);
 
		if(r <= tm) lc-> upt(l, r);
		else if(tm < l) rc-> upt(l, r);
		else {
			lc-> upt(l, tm);
			rc-> upt(tm + 1, r);
		}
 
		sum = lc-> sum + rc-> sum;
		if(lc-> lazy && rc-> lazy)
			lazy = 1;
	}
};
 
i64 gcd(i64 a, i64 b) {
	if(a == 0) return b;
	if(b == 0) return a;
	return gcd(b % a, a);
}
 
int main() {
	int n, gay = 0;
	i64 A, B;
	cin >> n >> A >> B;
	i64 T = A / gcd(A, B + 1) * B;
 
	// cout << T << endl;
	tree *root = new tree(0, T - 1);
 
	vector<pii> v;
	for(int i = 0; i < n; i++) {
		i64 l, r;
		cin >> l >> r;
		l %= T;
		r %= T;
 
		// cout << l << ' ' << r << endl;
 
		if(gay) continue;
		if(r - l + 1 >= T) {
			gay = 1;
			continue;
		}
 
		if(l <= r) {
			// cout << " > " << l << ' ' << r << endl;
			// root-> upt(l, r);
			v.push_back(MP(l, r));
		}
		else {
			// cout << " > " << l << ' ' << T - 1 << endl;
			// cout << " > " << 0 << ' ' << r << endl;
			// root-> upt(l, T - 1);
			// root-> upt(0, r);
			v.push_back(MP(l, T - 1));
			v.push_back(MP(0, r));
		}
	}
 
	if(gay) {
		cout << T << endl;
		return 0;
	}
 
	sort(v.begin(), v.end());
 
	i64 ans = 0;
	i64 l = 0, r = 0;
	for(pii p : v) {
		if(r < p.ff) {
			// cout << l << ' ' << r << endl;
			ans += (r - l + 1);
			l = p.ff;
		}
		r = p.ss;
	}
	// cout << l << ' ' << r << endl;
	ans += (r - l + 1);
	cout << ans << endl;
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:62:8: warning: unused variable 'root' [-Wunused-variable]
   62 |  tree *root = new tree(0, T - 1);
      |        ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1008 ms 17804 KB Output is correct
3 Correct 973 ms 51988 KB Output is correct
4 Correct 981 ms 51852 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1008 ms 17804 KB Output is correct
3 Correct 973 ms 51988 KB Output is correct
4 Correct 981 ms 51852 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 973 ms 51996 KB Output is correct
7 Correct 964 ms 52428 KB Output is correct
8 Correct 971 ms 52188 KB Output is correct
9 Incorrect 1091 ms 52656 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1008 ms 17804 KB Output is correct
3 Correct 973 ms 51988 KB Output is correct
4 Correct 981 ms 51852 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 102 ms 5824 KB Output is correct
7 Correct 99 ms 5628 KB Output is correct
8 Correct 114 ms 5808 KB Output is correct
9 Correct 110 ms 5796 KB Output is correct
10 Correct 98 ms 5596 KB Output is correct
11 Correct 101 ms 5804 KB Output is correct
12 Correct 99 ms 5800 KB Output is correct
13 Incorrect 110 ms 5736 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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