oj.uz

Submission #294679

# Submission time Handle Problem Language Result Execution time Memory
294679 2020-09-09T08:23:17 Z Plurm Strange Device (APIO19_strange_device) C++11
30 / 100
 4777 ms 413108 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);
			it = segmp[bckt].insert({r+1, tmpr}).first;
			ans += tmpr - r;
		}
	}
	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);
			it = segmp[bckt].insert({tmpl, l-1}).first;
			ans += l - tmpl;
		}
	}
	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[x].clear();
	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);
			it = blockmp.insert({r+1, tmpr}).first;
			ans += (tmpr - r) * b;
		}
	}
	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);
			it = blockmp.insert({tmpl, l-1}).first;
			ans += (l - tmpl) * b;
		}
	}
	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:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d%lld%lld",&n,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |   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 0 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 384 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 640 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 1560 ms 157172 KB Output is correct
3 Correct 4477 ms 376972 KB Output is correct
4 Correct 4777 ms 413108 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 1560 ms 157172 KB Output is correct
3 Correct 4477 ms 376972 KB Output is correct
4 Correct 4777 ms 413108 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Incorrect 3930 ms 319300 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 1560 ms 157172 KB Output is correct
3 Correct 4477 ms 376972 KB Output is correct
4 Correct 4777 ms 413108 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 177 ms 25876 KB Output is correct
7 Incorrect 267 ms 32228 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 1 ms 256 KB Output is correct
2 Correct 105 ms 10232 KB Output is correct
3 Correct 86 ms 10616 KB Output is correct
4 Correct 1305 ms 126840 KB Output is correct
5 Correct 95 ms 11516 KB Output is correct
6 Correct 97 ms 11512 KB Output is correct
7 Correct 95 ms 11512 KB Output is correct
8 Correct 104 ms 13560 KB Output is correct
9 Correct 103 ms 13688 KB Output is correct
10 Correct 85 ms 10360 KB Output is correct
11 Correct 105 ms 10232 KB Output is correct
12 Correct 86 ms 10232 KB Output is correct
13 Correct 101 ms 12024 KB Output is correct
14 Correct 893 ms 63480 KB Output is correct
15 Correct 82 ms 9720 KB Output is correct
16 Correct 942 ms 63352 KB Output is correct
17 Correct 1320 ms 122172 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 0 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 -