题目描述

Farmer John的农场边上的高速公路最近出现了引人注目的流量上升，或者至少Farmer John看起来是这样的。为了证实这件事，他打算用一组传感器测量公路上的车流量，每个传感器被用来测量一小段路面上的车流量的数值。
不幸的是，某一天经过牛棚的时候，Farmer John被绊倒了，装有传感器的盒子掉进了一个巨大的奶缸，之后它们就不能正常工作了。比起之前可以产生一个精确的车流量读数，现在每个传感器只能输出一个可能结果的范围。例如，一个传感器可能会给出范围[7,13][7,13]，表示在这段路面上的车流量不小于7，并且不大于13。

高速公路经过农场的这一段长N英里，车辆仅从一个方向通过公路，从第1英里驶向第N英里。Farmer John想要安装N个传感器——每一个监测高速公路上1英里长的路段。在其中某些路段上，有能够使得车辆进入高速公路的上匝道；在所有这样的路段上，Farmer John会将传感器装在上匝道上，测量流入的（近似）车流量。在某些路段上有能够使得车辆离开高速公路的下匝道；在所有这样的路段上，Farmer John会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下匝道，Farmer John就将传感器装在高速公路的主路上。

给定Farmer John的NN个传感器的读数，请求出在高速公路第1英里之前和第N英里之后车流量的最为准确的可能范围。这些范围应当与所有N个传感器的读数相一致。

输入描述:

输入的第一行包含N（1≤N≤100）。余下N行每行按从第11英里至第N英里的顺序描述一段1英里长的路段。每行包含一个字符串，为"on"（如果这段路上有一个上匝道），"off"（如果这段路上有一个下匝道），或者是"none"（如果这段路上没有匝道），然后是两个范围为0…1000的整数，表示这段路上的传感器的读数所给出的下界、上界。如果这段路上包含匝道，传感器读数来自于匝道，否则来自于主路。至少一个高速公路路段的描述会是"none"。

输出描述:

输出的第一行包含两个整数，为第1英里之前的车流量的最准确的可能范围。第二行包含两个整数，为第NN英里之后的车流量的最准确的可能范围。输入保证存在符合要求的解。

示例1

输入
4
on 1 1
none 10 14
none 11 15
off 2 3
输出
10 13
8 12
说明
在这个例子中，路段2和路段3的读数组合在一起告诉我们通过这两个路段的车流量为范围[11,14][11,14]之间的某个值，因为只有这个范围与两个读数[10,14][10,14]和[11,15][11,15]均一致。在第1英里，恰有1单位的车辆通过上匝道进入，所以在第1英里之前，车流量一定在范围[10,13][10,13]之内。在第4英里，2单位到3单位之间的车辆通过下匝道离开，所以这段路之后可能的车流量范围为[8,12][8,12]。

备注:

（1≤N≤100）
其他读入的数在[0,1000]之间

解答

起点1车辆的限制由起点到最右边的平路决定，终点N的车辆限制由终点到最左边的平路决定。

一个类似区间贪心的东西就可以了，100的数据范围时间复杂度竟然是O(n),我怀疑是放了一个网络流的烟雾弹

题目不难但不知道为什么没什么人过 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++) 
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f)) 
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x); 
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x); 
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long 
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
struct road{
    int op,l,r;
}r[maxn];
int main(){
    Sca(N);
    for(int i = 1; i <= N ; i ++){
        char op[5];
        scanf("%s%d%d",op,&r[i].l,&r[i].r);
        if(op[0] == 'n') r[i].op = 1;
        else if(op[1] == 'n') r[i].op = 2;
        else r[i].op = 3;  
    }
    int f = 0;
    for(int i = N ; i >= 1; i --){
        if(r[i].op == 1){
            f = i;
            break;
        }
    }
    int L = r[f].l,R = r[f].r;
    for(int i = f - 1; i >= 1; i --){
        if(r[i].op == 1){
            R = min(R,r[i].r);
            L = max(L,r[i].l);
        }else if(r[i].op == 2){
            R -= r[i].l; R = max(R,0);
            L -= r[i].r;
            L = max(L,0);
        }else{
            L += r[i].l;
            R += r[i].r;
        }
    }
    printf("%d %d\n",L,R);
    for(int i = 1; i <= N; i ++){
        if(r[i].op == 1){
            f = i;
            break;
        }
    }
    L = r[f].l,R = r[f].r;
    for(int i = f + 1; i <= N; i ++){
        if(r[i].op == 1){
            R = min(R,r[i].r);
            L = max(L,r[i].l);
        }else if(r[i].op == 3){
            R -= r[i].l; R = max(R,0);
            L -= r[i].r;
            L = max(L,0);
        }else{
            L += r[i].l;
            R += r[i].r;
        }
    }
    printf("%d %d\n",L,R);
    return 0;
}

来源：Hugh_Locke