欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces-816B Karen and Coffee

程序员文章站 2022-04-02 22:04:28
...

CodeForces-816B Karen and Coffee

题意: 给定一些区间和查询以及一个数k, 查询[l, r]区间内出现了大于等于k次的区间长度的总和.
分析: 预处理区间, 给定区间的首和尾记录下来, 在判断是否大于等于k, 进行累加即可, 详情见代码.
代码:

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 10;
int a[MAXN], b[MAXN];
int main()
{
    int n, k, q;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cin >> n >> k >> q;
    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        a[l]++, a[r + 1]--;
    }

    int t = 0;

    for (int i = 1; i < MAXN; i++)
    {
        t += a[i];
        if (t >= k)
            b[i] = b[i - 1] + 1;
        else
            b[i] = b[i - 1];
    }

    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << b[r] - b[l - 1] << endl;
    }
}
相关标签: 思维