建议降为红/橙题
  • 板块CF44C Holidays
  • 楼主AllenReder
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/15 22:16
  • 上次更新2024/3/16 09:27:49
查看原帖
建议降为红/橙题
267730
AllenReder楼主2024/3/15 22:16

用不用树状数组都能过:

#include <iostream>
using namespace std;

const int N = 1e3 + 10;

int n, m;
int a[N], b[N];

int t[N];

int lowbit(int x) { return x & -x; }

void add(int x, int val) {
    while (x <= n) {
        t[x] += val;
        x += lowbit(x);
    }
}

int sum(int x) {
    int ret = 0;
    while (x) {
        ret += t[x];
        x -= lowbit(x);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i];
        add(a[i], 1);
        add(b[i] + 1, -1);
    }
    for (int i = 1; i <= n; ++i) {
        int i_sum = sum(i);
        if (i_sum != 1) {
            cout << i << " " << i_sum << endl;
            return 0;
        }
    }
    cout << "OK" << endl;
    return 0;
}
#include <iostream>
using namespace std;

const int N = 1e3 + 10;

int n, m;
int a[N];
int b[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        cin >> l >> r;
        b[l]++, b[r + 1]--;
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + b[i];
        if (a[i] != 1) {
            cout << i << " " << a[i] << endl;
            return 0;
        }
    }
    cout << "OK" << endl;
    return 0;
}
2024/3/15 22:16
加载中...