codeforces469B

Chat Online

问题描述

你和你的朋友经常在网上聊天.
你的朋友作息规律每天只会在p个时间段[ai,bi]在线.
你作息混乱,假设你在t时刻起床,那么你会在q个时间段[t+ci,t+di]在线.
现在,你有可能会在[l,r]的这个时间段中的任意一个时刻起床,假设你在t时刻起床,请问有多少个这样的t使得你有机会和你的朋友聊天?
只要你们在线的时间有哪怕一刻重合,你就可以和你的朋友聊天
输入格式

第一行4个整数p,q,l,r.(1<=p,q<=50;0<=l<=r<=1000)
接下来p行,每行两个整数ai,bi.(表示你的朋友的p个在线时间段)
接下来q行,每行两个整数ci,di.(表示你的第i个在线时间段的参数)
0<=ai< bi <=1000
0<=ci< di <=1000
保证b[i]< a[i+1]以及d[i]< c[i+1].
题中涉及到的区间都是闭区间,时刻都只考虑整数.输出格式输出只有一个整数,表示满足要求的t的个数.样例

样例输入1

1 1 0 4
2 3
0 1

样例输出1

样例输入2

样例输出2

20

sol：暴力模拟就好了
Ps：判断区间[a,b]和[c,d]有交集当且仅当a<=d且b>=c

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=55;
int n,m;
int a[N],b[N],c[N],d[N];
int main()
{
    int i,j,k,L,R,ans=0;
    R(n); R(m); R(L); R(R);
    for(i=1;i<=n;i++)
    {
        R(a[i]); R(b[i]);
    }
    for(i=1;i<=m;i++)
    {
        R(c[i]); R(d[i]);
    }
    for(i=L;i<=R;i++)
    {
        bool Bo=0;
        for(j=1;j<=n&&(!Bo);j++)
        {
            bool Flag=0;
            for(k=1;k<=m&&(!Flag);k++)
            {
                if(c[k]+i<=b[j]&&d[k]+i>=a[j]) Flag=1;
            }
            if(Flag) Bo=1;
        }
        ans+=Bo;
    }
    Wl(ans);
    return 0;
}
/*
input
1 1 0 4
2 3
0 1
output
3

input
2 3 0 20
15 17
23 26
1 4
7 11
15 17
output
20
*/

View Code