Submission #162152

#	Time	Username	Problem	Language	Result	Execution time	Memory
162152		Berted	Strange Device (APIO19_strange_device)	C++14	5 / 100	3 ms	536 KiB

strange_device

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define ll long long
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define fst first
#define snd second
#define pub push_back

using namespace std;
vector<pii> cr,cr2;
vector<ppi> dt;
priority_queue<pii,vector<pii>,greater<pii>> pq;
unordered_map<ll,ll> mp;
ll n,a,b,t,crto = 0,rs = 0,l,r;
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
int main()
{
	scanf("%lld %lld %lld",&n,&a,&b);
	t = a / gcd(a,b+1);
	for (int i=0;i<n;i++)
	{
		scanf("%lld %lld %lld",&l,&r);
		if (l/b == r/b) {dt.push_back({{l%b,r%b},(l/b)%t});}
		else
		{
			if (r%b != b-1) {dt.push_back({{0,r%b},(r/b)%t});}
			if (l%b != 0) {dt.push_back({{l%b,b-1},(l/b)%t});}
			if ((l+(b-1))/b <= (r-(b-1))/b) 
			{
				ll l2 = ((l+(b-1))/b)%t;
				ll r2 = ((r-(b-1))/b)%t;
				if (((r-(b-1))/b) - ((l+(b-1))/b) >= t) {cr.pub({0,t-1});}
				else if (l2<=r2) {cr.pub({l2,r2});}
				else {cr.pub({l2,t-1});cr.pub({0,r2});}
			} 
		}
		
	}
	sort(dt.begin(),dt.end());
	sort(cr.begin(),cr.end());
	
	l = -1,r = -2;
	for (int i=0;i<cr.size();i++)
	{
		if (r+1<cr[i].fst)
		{
			if (l!=-1) {cr2.pub({l,r});crto += r - l + 1;}
			l = cr[i].fst;
			r = cr[i].fst;
		}
		r = max(r,cr[i].snd);
	}
	if (l!=-1) {cr2.pub({l,r});crto += r - l + 1;}
	//cr.clear();
	/*
	cout<<"-- DT --\n";
	for (int i=0;i<dt.size();i++)
	{
		cout<<dt[i].fst.fst<<" "<<dt[i].fst.snd<<" "<<dt[i].snd<<"\n";
	}
	cout<<"-- CR2 --\n";
	for (int i=0;i<cr2.size();i++)
	{
		cout<<cr2[i].fst<<" "<<cr2[i].snd<<"\n";
	}
	*/
	ll pv = 0;
	for (int i=0;i<dt.size();i++) 
	{
		while (pq.size())
		{
			if (pq.top().fst < dt[i].fst.fst)
			{
				rs += crto * (pq.top().fst+1-pv);
				pv = pq.top().fst+1;
				mp[pq.top().snd]--;
				if (mp[pq.top().snd]==0) {crto--;}
				pq.pop();
			}
			else {break;}
		}
		//cout<<i<<" "<<crto<<" "<<rs<<" "<<pv<<"\n";
		auto it = upper_bound(cr2.begin(),cr2.end(),make_pair(dt[i].snd+1,(ll)-1));
		if (it != cr2.begin())
		{
			it = prev(it);
			if (dt[i].snd > (it->snd))
			{
				rs += crto * (dt[i].fst.fst-pv);
				pv = dt[i].fst.fst;
				mp[dt[i].snd]++;
				if (mp[dt[i].snd]==1) {crto++;}
				pq.push({dt[i].fst.snd,dt[i].snd});
			}
		}
		else
		{
			rs += crto * (dt[i].fst.fst-pv);
			pv = dt[i].fst.fst;
			mp[dt[i].snd]++;
			if (mp[dt[i].snd]==1) {crto++;}
			pq.push({dt[i].fst.snd,dt[i].snd});
		}
		//cout<<i<<" "<<crto<<" "<<rs<<" "<<pv<<"\n";
	}
	while (pq.size())
	{
		rs += crto * (pq.top().fst+1-pv);
		pv = pq.top().fst+1;
		mp[pq.top().snd]--;
		if (mp[pq.top().snd]==0) {crto--;}
		pq.pop();
	}
	rs += crto * (b - pv);
	printf("%lld\n",rs);
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:26:31: warning: format '%lld' expects a matching 'long long int*' argument [-Wformat=]
   scanf("%lld %lld %lld",&l,&r);
                               ^
strange_device.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<cr.size();i++)
               ~^~~~~~~~~~
strange_device.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<dt.size();i++) 
               ~^~~~~~~~~~
strange_device.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30