oj.uz

Submission #162148

# Submission time Handle Problem Language Result Execution time Memory
162148 2019-11-06T17:08:42 Z Berted Strange Device (APIO19_strange_device) C++14
20 / 100
 1929 ms 139208 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <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;
map<ll,ll> mp;
ll n,a,b,t,crto = 0,rs = 0;
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>a>>b;
	t = a / gcd(a,b+1);
	for (int i=0;i<n;i++)
	{
		ll l,r;cin>>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 (l2<=r2) {cr.pub({l2,r2});}
				else {cr.pub({r2,t-1});cr.pub({0,l2});
				}
			} 
		}
		
	}
	sort(dt.begin(),dt.end());
	sort(cr.begin(),cr.end());
	
	ll 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);
	cout<<rs<<"\n";
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<cr.size();i++)
               ~^~~~~~~~~~
strange_device.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<dt.size();i++) 
               ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 11 ms 1208 KB Output is correct
3 Correct 10 ms 1212 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1929 ms 139208 KB Output is correct
3 Incorrect 691 ms 53440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1929 ms 139208 KB Output is correct
3 Incorrect 691 ms 53440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1929 ms 139208 KB Output is correct
3 Incorrect 691 ms 53440 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 2 ms 376 KB Output is correct
2 Correct 90 ms 6620 KB Output is correct
3 Correct 114 ms 6628 KB Output is correct
4 Correct 1851 ms 102332 KB Output is correct
5 Correct 119 ms 7392 KB Output is correct
6 Correct 123 ms 7276 KB Output is correct
7 Correct 116 ms 7264 KB Output is correct
8 Correct 135 ms 8676 KB Output is correct
9 Correct 142 ms 8800 KB Output is correct
10 Correct 103 ms 6628 KB Output is correct
11 Correct 74 ms 6628 KB Output is correct
12 Correct 85 ms 6756 KB Output is correct
13 Correct 122 ms 7552 KB Output is correct
14 Correct 1067 ms 61436 KB Output is correct
15 Correct 94 ms 6668 KB Output is correct
16 Correct 943 ms 61228 KB Output is correct
17 Correct 1714 ms 99384 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 11 ms 1208 KB Output is correct
3 Correct 10 ms 1212 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -