oj.uz

Submission #162149

# Submission time Handle Problem Language Result Execution time Memory
162149 2019-11-06T17:15:23 Z Berted Strange Device (APIO19_strange_device) C++14
65 / 100
 3669 ms 194340 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({l2,t-1});cr.pub({0,r2});
				}
			} 
		}
		
	}
	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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 1208 KB Output is correct
3 Correct 11 ms 1208 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1208 KB Output is correct
17 Correct 85 ms 6628 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 525 ms 41424 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1952 ms 102064 KB Output is correct
3 Correct 684 ms 17232 KB Output is correct
4 Correct 704 ms 53376 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1952 ms 102064 KB Output is correct
3 Correct 684 ms 17232 KB Output is correct
4 Correct 704 ms 53376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3505 ms 194320 KB Output is correct
7 Correct 1630 ms 87296 KB Output is correct
8 Correct 3572 ms 194040 KB Output is correct
9 Correct 3568 ms 194304 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1952 ms 102064 KB Output is correct
3 Correct 684 ms 17232 KB Output is correct
4 Correct 704 ms 53376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 247 ms 16632 KB Output is correct
7 Correct 272 ms 19724 KB Output is correct
8 Correct 263 ms 19776 KB Output is correct
9 Correct 264 ms 19724 KB Output is correct
10 Correct 186 ms 14424 KB Output is correct
11 Correct 247 ms 19716 KB Output is correct
12 Correct 266 ms 19804 KB Output is correct
13 Correct 294 ms 19736 KB Output is correct
14 Correct 73 ms 6500 KB Output is correct
15 Correct 272 ms 17128 KB Output is correct
16 Correct 109 ms 6632 KB Output is correct
17 Correct 342 ms 19796 KB Output is correct
18 Correct 3381 ms 194296 KB Output is correct
19 Correct 3478 ms 194340 KB Output is correct
20 Correct 3669 ms 194232 KB Output is correct
21 Correct 265 ms 19816 KB Output is correct
22 Correct 283 ms 19904 KB Output is correct
23 Correct 227 ms 18528 KB Output is correct

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 5864 KB Output is correct
3 Correct 107 ms 5300 KB Output is correct
4 Correct 1901 ms 65444 KB Output is correct
5 Correct 118 ms 5604 KB Output is correct
6 Correct 117 ms 5480 KB Output is correct
7 Correct 115 ms 5480 KB Output is correct
8 Correct 133 ms 6780 KB Output is correct
9 Correct 131 ms 7008 KB Output is correct
10 Correct 106 ms 5952 KB Output is correct
11 Correct 74 ms 5992 KB Output is correct
12 Correct 85 ms 5992 KB Output is correct
13 Correct 124 ms 6240 KB Output is correct
14 Correct 1068 ms 25436 KB Output is correct
15 Correct 94 ms 5992 KB Output is correct
16 Correct 925 ms 25464 KB Output is correct
17 Correct 1657 ms 62580 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 376 KB Output is correct
2 Correct 11 ms 1208 KB Output is correct
3 Correct 11 ms 1208 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1208 KB Output is correct
17 Correct 85 ms 6628 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 6 ms 352 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Incorrect 2 ms 376 KB Output isn't correct
23 Halted 0 ms 0 KB -