oj.uz

Submission #294697

# Submission time Handle Problem Language Result Execution time Memory
294697 2020-09-09T08:36:22 Z Plurm Strange Device (APIO19_strange_device) C++11
30 / 100
 4763 ms 376660 KB 
#include <bits/stdc++.h>
#define long long long
using namespace std;
long a, b;
set<pair<long,long> > blockmp;
map<long, set<pair<long,long> > > segmp;
long ans;
void addSegment(long bckt, long l, long r){
	auto bit = blockmp.lower_bound({bckt+1,0});
	if(bit != blockmp.begin()){
		bit--;
		if(bit->second >= bckt) return;
	}
	auto cit = segmp[bckt].lower_bound({l+1, 0});
	if(cit != segmp[bckt].begin()){
		cit--;
		if(cit->second >= r) return;
	}
	auto it = segmp[bckt].lower_bound({l, 0});
	while(it != segmp[bckt].end() && it->first <= r){
		if(it->second <= r){
			ans -= it->second - it->first + 1;
			it = segmp[bckt].erase(it);
		}else{
			ans -= it->second - it->first + 1;
			long tmpr = it->second;
			segmp[bckt].erase(it);
			segmp[bckt].insert({r+1, tmpr}).first;
			ans += tmpr - r;
			break;
		}
	}
	it = segmp[bckt].lower_bound({r+1, 0});
	while(it != segmp[bckt].begin()){
		--it;
		if(it->second < l) break;
		if(it->first >= l){
			ans -= it->second - it->first + 1;
			it = segmp[bckt].erase(it);
		}else{
			ans -= it->second - it->first + 1;
			long tmpl = it->first;
			segmp[bckt].erase(it);
			segmp[bckt].insert({tmpl, l-1}).first;
			ans += l - tmpl;
			break;
		}
	}
	segmp[bckt].emplace(l, r);
	ans += r - l + 1;
}
void addBlock(long l, long r){
	auto bit = blockmp.lower_bound({l+1,0});
	if(bit != blockmp.begin()){
		bit--;
		if(bit->second >= r) return;
	}
	auto st = segmp.lower_bound(l);
	auto ft = segmp.upper_bound(r);
	vector<long> v;
	for(auto it = st; it != ft; it++){
		for(auto p : it->second) ans -= p.second - p.first + 1;
		it->second.clear();
		v.push_back(it->first);
	}
	for(long x : v) segmp.erase(x);
	auto it = blockmp.lower_bound({l, 0});
	while(it != blockmp.end() && it->first <= r){
		if(it->second <= r){
			ans -= (it->second - it->first + 1) * b;
			it = blockmp.erase(it);
		}else{
			ans -= it->second - it->first + 1;
			long tmpr = it->second;
			blockmp.erase(it);
			blockmp.insert({r+1, tmpr}).first;
			ans += (tmpr - r) * b;
			break;
		}
	}
	it = blockmp.lower_bound({r+1, 0});
	while(it != blockmp.begin()){
		--it;
		if(it->second < l) break;
		if(it->first >= l){
			ans -= (it->second - it->first + 1) * b;
			it = blockmp.erase(it);
		}else{
			ans -= (it->second - it->first + 1) * b;
			long tmpl = it->first;
			blockmp.erase(it);
			blockmp.insert({tmpl, l-1}).first;
			ans += (l - tmpl) * b;
			break;
		}
	}
	ans += (r-l+1) * b;
	blockmp.emplace(l, r);
}
int main(){
	int n;
	scanf("%d%lld%lld",&n,&a,&b);
	long g = __gcd(a, b+1ll);
	long crit = a / g;
	for(int i = 1; i <= n; i++){
		long l, r;
		scanf("%lld%lld",&l,&r);
		if(l/b == r/b){
			addSegment((l/b) % crit, l % b, r % b);
			continue;
		}
		long sa = l / b;
		addSegment(sa % crit, l % b, b-1);
		long fa = r / b;
		addSegment(fa % crit, 0, r % b);
		long res = (sa+1) % crit;
		if((fa-1) - (sa+1) >= crit){
			// answer = crit * b
			printf("%lld\n", crit * b);
			return 0;
		}
		if(res + (fa-1) - (sa+1) >= crit){
			// res to crit-1
			addBlock(res, crit-1);
			// 0 to (fa-1) % crit
			addBlock(0, (fa-1) % crit);
		}else if(sa+1 <= fa-1){
			addBlock(res, (fa-1) % crit);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d%lld%lld",&n,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%lld%lld",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1491 ms 157304 KB Output is correct
3 Correct 4462 ms 376256 KB Output is correct
4 Correct 4763 ms 376660 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1491 ms 157304 KB Output is correct
3 Correct 4462 ms 376256 KB Output is correct
4 Correct 4763 ms 376660 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Incorrect 3909 ms 282184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1491 ms 157304 KB Output is correct
3 Correct 4462 ms 376256 KB Output is correct
4 Correct 4763 ms 376660 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 180 ms 24184 KB Output is correct
7 Incorrect 263 ms 30404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 93 ms 8520 KB Output is correct
3 Correct 87 ms 8824 KB Output is correct
4 Correct 1341 ms 126840 KB Output is correct
5 Correct 96 ms 9848 KB Output is correct
6 Correct 102 ms 9700 KB Output is correct
7 Correct 92 ms 9848 KB Output is correct
8 Correct 106 ms 11896 KB Output is correct
9 Correct 105 ms 12024 KB Output is correct
10 Correct 82 ms 8568 KB Output is correct
11 Correct 97 ms 8568 KB Output is correct
12 Correct 83 ms 8568 KB Output is correct
13 Correct 95 ms 10232 KB Output is correct
14 Correct 907 ms 63864 KB Output is correct
15 Correct 81 ms 7928 KB Output is correct
16 Correct 959 ms 63652 KB Output is correct
17 Correct 1310 ms 122312 KB Output is correct
18 Correct 1 ms 256 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -