原题：
ACM International Col legiate Programming Contest Asia Regional Contest, Tsukuba, 2016–10–16 Problem C Distribution Center Input: Standard Input Time Limit: 3 seconds The factory of the Impractically Complicated Pro ducts Corp oration has many manufacturing lines and the same numb er of corresp onding s torage ro oms. The same numb er of conveyor lanes are laid out in parallel to transfer go o ds from manufacturing lines dire ctly to the corresp onding storage ro oms. Now, they plan to install a numb er of rob ot arms he re and there b etween pairs of adjacent conveyor lanes so that go o ds in one of the lanes c an b e picked up and released down on the other, and also in the opp osite way. This should allow mixing up go o ds from different manufacturing lines to the storage ro om s. Dep ending on the p os itions of rob ot arms, the go o ds from each of the manufacturing lines can only b e delivered to some of the storage ro oms. Your task is to find the numb er of manufacturing lines from which go o ds c an b e transferred to each of the storage ro oms, given the numb er of conveyor lanes and p ositions of rob ot arms. Input The input consists of a single test case, formatted as follows. n m x 1 y 1 .x m y m An integer n (2 ≤ n ≤ 200000) in the first line is the number of conveyor lanes. The lanes are numbered from 1 to n, and two lanes with their numbers differing with 1 are adjacent. All of them start from the position x = 0 and end at x = 100000. The other integer m (1 ≤ m < 100000) is the number of robot arms. The following m lines indicate the positions of the robot arms by two integers x i (0 < x i < 100000) and y i (1 ≤ y i < n). Here, x i is the x-coordinate of the i-th robot arm, which can pick goods on either the lane y i or the lane y i + 1 at position x = x i, and then release them on the other at the same x-coordinate. You can assume that positions of no two robot arms have the same x-coordinate, that is, x i 6= x j for any i 6= j. 7 lane 1 lane 2 lane 3 lane 4 manufacturing lines storage rooms =⇒ Figure C.1. Illustration of Sample Input 1 Output Output n integers separated by a space in one line. The i-th integer is the number of the manufacturing lines from which the storage room connected to the conveyor lane i can accept goods. Sample Input 1 Sample Output 1 4 3 1000 1 2000 2 3000 3 2 3 4 4 Sample Input 2 Sample Output 2 4 3 1 1 3 2 2 3 2 4 4 2
题意：
每两条生产线间有多个机械手臂，可以在生产线间移动货物，求每条生产线上最多有多少种货物。
思路：
将机械手臂按位置排序，每条生产线的可以出现的货物区间不停更新。
#include <iostream> #include <iomanip> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <deque> #include <stack> #include <string> #include <cmath> #include <vector> #include <utility> #include <set> #include <map> #include <sstream> #include <climits> //#pragma comment(linker, "/STACK:1024000000,1024000000") #define pi acos(-1.0) #define INF 0x3f3f3f3f using namespace std; const int maxn = 2 * 1e5 + 10; int n, m, ans[maxn]; struct Rob { int x,id; } rob[maxn]; struct Line { int ans,up,down; } line[maxn]; bool cmp(const Rob&a,const Rob&b) { return a.x<b.x; } int main () { scanf("%d%d",&n,&m); for(int i=0; i<maxn; i++) rob[i].x=INF,rob[i].id=INF; for(int i=0; i<n; i++) line[i].ans=1,line[i].up=i,line[i].down=i; for(int i=0; i<m; i++) { int a,b; scanf("%d%d",&a,&b); rob[i].x=a; rob[i].id=b; } sort(rob,rob+m,cmp); for(int i=0; i<m; i++) { line[rob[i].id-1].down=line[rob[i].id].down; line[rob[i].id].up=line[rob[i].id-1].up; line[rob[i].id-1].ans= line[rob[i].id-1].down- line[rob[i].id-1].up+1; line[rob[i].id].ans= line[rob[i].id].down- line[rob[i].id].up+1; } for(int i=0; i<n; i++) if(i==0) printf("%d",line[i].ans); else printf(" %d",line[i].ans); printf("\n"); return 0; }
