oj.uz

Submission #294672

# Submission time Handle Problem Language Result Execution time Memory
294672 2020-09-09T08:17:59 Z Plurm Strange Device (APIO19_strange_device) C++11
25 / 100
 4282 ms 413148 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 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:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%lld%lld",&n,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%lld%lld",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 10 ms 1400 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 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 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 91 ms 10232 KB Output is correct
3 Correct 83 ms 10616 KB Output is correct
4 Correct 1301 ms 163520 KB Output is correct
5 Correct 110 ms 11640 KB Output is correct
6 Correct 94 ms 11512 KB Output is correct
7 Correct 91 ms 11640 KB Output is correct
8 Correct 104 ms 13560 KB Output is correct
9 Correct 103 ms 13816 KB Output is correct
10 Correct 82 ms 10488 KB Output is correct
11 Correct 97 ms 10360 KB Output is correct
12 Correct 102 ms 10364 KB Output is correct
13 Correct 94 ms 12048 KB Output is correct
14 Correct 979 ms 100468 KB Output is correct
15 Correct 115 ms 9720 KB Output is correct
16 Correct 1041 ms 100312 KB Output is correct
17 Correct 1321 ms 158932 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 1 ms 256 KB Output is correct
2 Correct 10 ms 1400 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 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 -