提出 #74602428

---

ソースコード 拡げる

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXM = 100010;    // M,Q最大1e5
const int MAXNODE = 2000010; // 主席树节点数（20倍M）

// 主席树核心数组
int tot;                // 节点总数
int root[MAXM];         // 每个前缀的根节点
int lc[MAXNODE], rc[MAXNODE]; // 左右孩子
int cnt[MAXNODE];       // 节点计数
vector<int> ds;         // 离散化数组（存储所有页数）

// 主席树更新：新建版本
int update(int pre, int l, int r, int x) {
    int now = ++tot;
    lc[now] = lc[pre];
    rc[now] = rc[pre];
    cnt[now] = cnt[pre] + 1;
    if (l == r) return now;
    int mid = (l + r) >> 1;
    if (x <= mid)
        lc[now] = update(lc[pre], l, mid, x);
    else
        rc[now] = update(rc[pre], mid + 1, r, x);
    return now;
}

// 主席树查询：统计[1, x-1]的数量（小于x的元素个数）
int query(int u, int v, int l, int r, int x) {
    if (x <= l) return 0;
    if (r < x) return cnt[v] - cnt[u];
    int mid = (l + r) >> 1;
    return query(lc[u], lc[v], l, mid, x) + query(rc[u], rc[v], mid + 1, r, x);
}

// 离散化获取排名
int get_rank(int x) {
    return lower_bound(ds.begin(), ds.end(), x) - ds.begin() + 1;
}

int main() {
    int N, M, Q, K;
    scanf("%d%d%d%d", &N, &M, &Q, &K);
    
    vector<pair<int, int> > books; // (书架编号S, 页数D)
    books.reserve(M);
    ds.reserve(M);
    
    // 输入书籍信息
    for (int i = 0; i < M; ++i) {
        int s, d;
        scanf("%d%d", &s, &d);
        books.push_back(make_pair(s, d));
        ds.push_back(d);
    }
    
    // 1. 离散化：排序+去重
    sort(ds.begin(), ds.end());
    ds.erase(unique(ds.begin(), ds.end()), ds.end());
    int len = ds.size();
    
    // 2. 按书架编号排序书籍
    sort(books.begin(), books.end());
    
    // 3. 构建主席树
    tot = 0;
    root[0] = 0;
    int p = 0; // 书籍指针
    for (int i = 1; i <= N; ++i) {
        root[i] = root[i-1];
        // 插入当前书架的所有书籍
        while (p < M && books[p].first == i) {
            int rk = get_rank(books[p].second);
            root[i] = update(root[i], 1, len, rk);
            p++;
        }
    }
    
    // 4. 处理查询
    while (Q--) {
        int L, R, T;
        scanf("%d%d%d", &L, &R, &T);
        int rk = get_rank(T);
        // 区间[L,R]总书数
        int total = cnt[root[R]] - cnt[root[L-1]];
        // 小于T的书数
        int less = query(root[L-1], root[R], 1, len, rk);
        // 页数≥T的书数
        int C = total - less;
        // 最终答案
        int ans = C - K > 0 ? C - K : 0;
        printf("%d\n", ans);
    }
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:46:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |     scanf("%d%d%d%d", &N, &M, &Q, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |         scanf("%d%d", &s, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:85:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |         scanf("%d%d%d", &L, &R, &T);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ジャッジ結果