Submission #294679

#	Time	Username	Problem	Language	Result	Execution time	Memory
294679		Plurm	Strange Device (APIO19_strange_device)	C++11	30 / 100	4777 ms	413108 KiB

strange_device

#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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30