oj.uz

답안 #733155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733155 2023-04-30T07:28:55 Z minhcool 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 1703 ms 318532 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

/*
What I'm trying to do:
Just imagine that we want all intervals that begins with (sth, 0) to ((sth + B - 1) % A, B - 1), the rest
has like O(n) segments. Inside this interval, there will be no changes made to t/B
Ez as hell
*/

int n, a, b;

//vector<int> inters[N];
vector<ii> full;
unordered_map<int, int> mp;
bool ok[N];
vector<ii> part[N];

int cnt;

void process(){
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		int temp1 = x / b + 1, temp2 = y / b - 1;
		if(temp1 <= temp2){
			if((temp2 - temp1 + 1) >= a){
				cout << a * b;
				exit(0);
			}
			temp1 %= a, temp2 %= a;
			if(temp1 <= temp2) full.pb({temp1, temp2});
			else{
				full.pb({temp1, a - 1});
				full.pb({0, temp2});
			}
		}
		if((x/b) == (y/b)){
			if(mp.find((x/b) % a) == mp.end()){
				cnt++;
				mp[(x/b) % a] = cnt;
			}
		//	cout << x << " " << y << " " << cnt << " " << x%b << " " << y%b << "\n";
			part[mp[(x/b) % a]].pb({x % b, y % b});	
		}
		else{
			//temp1 = , temp2 = (y / b) * b;
			if(mp.find((x/b) % a) == mp.end()){
				cnt++;
				mp[(x/b) % a] = cnt;
			}
			part[mp[(x/b) % a]].pb({x % b, b - 1});
			//cout << x << " " << y << " " << cnt << " " << x%b << " " << b-1 << "\n";
			if(mp.find((y/b) % a) == mp.end()){
				cnt++;
				mp[(y/b) % a] = cnt;
			}
			part[mp[(y/b) % a]].pb({0, y % b});
		//	cout << x << " " << y << " " << cnt << " " << 0 << " " << y%b << "\n";
		}
	}
	//sort(full.begin(), full.end());
	vector<ii> updates;
	for(auto it : full){
		updates.pb({it.fi, 1});
		updates.pb({it.se + 1, -1});
	}
	for(auto it : mp) updates.pb({it.fi, oo});
	sort(updates.begin(), updates.end());
	int lst = -oo, sum = 0, ans = 0;
	for(auto it : updates){
		if(lst != -oo) ans += b * (it.fi - lst) * (sum != 0);
		lst = it.fi;
		if(abs(it.se) == 1) sum += it.se;
		if(it.se == oo) ok[mp[it.fi]] = (sum == 0);
	}
//	cout << ans << "\n";
//	for(auto it : mp) cout << it.fi << " " << it.se << "\n";
	for(int i = 1; i <= cnt; i++){
		if(!ok[i]) continue;
		sort(part[i].begin(), part[i].end());
		vector<ii> upds;
		for(auto it : part[i]){
	//		cout << i << " " << it.fi << " " << it.se << "\n";
			upds.pb({it.fi, 1});
			upds.pb({it.se + 1, -1});
		}
		sort(upds.begin(), upds.end());
		int lst = -oo, sum = 0;
		for(auto it : upds){
	//		cout << "OK " << sum << " " << lst << " " << it.fi << "\n";
			if(lst != -oo) ans += (it.fi - lst) * (sum != 0);
			sum += it.se;
			lst = it.fi;
		}
	//	cout << ans << "\n";
	}
	cout << ans << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 70736 KB Output is correct
2 Correct 54 ms 71448 KB Output is correct
3 Correct 46 ms 71252 KB Output is correct
4 Incorrect 41 ms 70724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70728 KB Output is correct
2 Correct 40 ms 70760 KB Output is correct
3 Correct 49 ms 70724 KB Output is correct
4 Correct 46 ms 70660 KB Output is correct
5 Correct 51 ms 70652 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70760 KB Output is correct
2 Correct 44 ms 70968 KB Output is correct
3 Correct 44 ms 70736 KB Output is correct
4 Correct 41 ms 70852 KB Output is correct
5 Correct 969 ms 199232 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 70672 KB Output is correct
2 Correct 850 ms 174316 KB Output is correct
3 Incorrect 1703 ms 318532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 70672 KB Output is correct
2 Correct 850 ms 174316 KB Output is correct
3 Incorrect 1703 ms 318532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 70672 KB Output is correct
2 Correct 850 ms 174316 KB Output is correct
3 Incorrect 1703 ms 318532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70740 KB Output is correct
2 Correct 86 ms 76088 KB Output is correct
3 Correct 88 ms 75932 KB Output is correct
4 Correct 713 ms 137912 KB Output is correct
5 Correct 95 ms 77260 KB Output is correct
6 Correct 89 ms 77044 KB Output is correct
7 Correct 86 ms 77260 KB Output is correct
8 Correct 99 ms 79092 KB Output is correct
9 Correct 112 ms 79140 KB Output is correct
10 Correct 87 ms 76160 KB Output is correct
11 Correct 94 ms 76588 KB Output is correct
12 Correct 85 ms 76520 KB Output is correct
13 Correct 92 ms 78088 KB Output is correct
14 Correct 547 ms 91700 KB Output is correct
15 Incorrect 91 ms 76748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 70736 KB Output is correct
2 Correct 54 ms 71448 KB Output is correct
3 Correct 46 ms 71252 KB Output is correct
4 Incorrect 41 ms 70724 KB Output isn't correct
5 Halted 0 ms 0 KB -