[daily question in summer] Luogu p1568 race

Topic link ：P1568 Race - Luogu | New ecology of computer science education (luogu.com.cn)

Background

Race

Title Description

SH My running performance has not been ideal . To help SH Improve your grades ,KC Decided to have a race with him . The starting point of the competition is in front of the farmer's house , They set out at the same time , In the same direction , Until the end ---- Under a tree far from the farm .

Their running speed is constant for some time . such as ：SH before ３ The speed for a period of time is ５, next ６ The speed in a period of time is １０. Their total game time is the same . They want to be able to count the number of changes in the leading order throughout the game . for instance , Some time SH leading , Next moment KC leading , This is a change in the leading order ; If at some point SH leading , For a while KC Catch up and talk to SH Do many things at once , But it finally surpassed SH, This is also a change in the leading order .

Input format

The first １ That's ok ：N and M（1 <= N, M <= 1000）.

Next N That's ok ： Two integers per line , describe SH A run , Respectively represent the paragraph SH The speed of running and the duration of this speed . All data ranges [1..1000].

And then the next M That's ok ： Two integers per line , describe KC A run , Respectively represent the paragraph KC The speed of running and the duration of this speed . All data ranges [1..1000].

Output format

a line ： The number of changes in the leading order during the whole competition .

Examples #1

The sample input #1

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

Sample output #1

2

Tips

Input ：SH before ２ The speed per unit time is １, next １ The speed per unit time is ４, next １ The speed per unit time is １, Last １０ The speed per unit time is ２.KC before ３ The speed per unit time is ２, next ２ The speed per unit time is １, Last 9 The speed per unit time is ３.

Output ： After the game starts KC leading , Until the first ５ Unit time SH exceed KC（ The first leading order change ）, And then ７ Unit time ,KC Anti super SH, Become a leader （ The second leading order change ）.

AC code:（ Be sure to turn it on long long！！！）

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
	typedef long long ll;
	vector<ll> s1,s2;
	ll n,m;
	cin>>n>>m;
	ll s=0;
	while(n--)
	{
		ll a,b;
		cin>>a>>b;
		while(b--)
		{
			s+=a;
			s1.push_back(s);
		}
	}
	
	s=0;
	while(m--)
	{
		ll a,b;
		cin>>a>>b;
		while(b--)
		{
			s+=a;
			s2.push_back(s);
		}
	}
	
	//i+1                1 2 3 4 5 6  7  8  9  10 11 12 13 14
	//s1[i]              1 2 6 7 9 11 13 15 17 19 21 23 25 27
	//s2[i]              2 4 6 7 8 11 14 17 20 23 26 29 32 35
	//s2[i]-s1[i]        1 2 0 0 -1 0 1  2  3  4  5  6  7  8
	
	ll cnt=0;
	vector<ll> res;
	for(ll i=0;i<s1.size();i++)
	{
		if(s1[i]!=s2[i]) //  Route difference (s2[i]-s1[i])==0 Do not put  
			res.push_back(s2[i]-s1[i]);
	}

	for(ll i=1;i<res.size();i++)
		if(res[i]*res[i-1]<0)
			cnt++;
	
	cout<<cnt;
	
	return 0;
}