제출 #20505

#제출 시각아이디문제언어결과실행 시간메모리
20505CYI (#35)초음속철도 (OJUZ11_rail)C++14
0 / 100
579 ms12836 KiB
#include<cstdio>
#include<algorithm>
#define mod 1000000007
using namespace std;
const int MXM = 2e5;
typedef long long ll;
int n, m, idx[MXM + 2], sz=1;
pair<int, int> p[MXM];
struct st {
    int s, a = 1, b;
}tree[MXM * 4];
void f(int h, int a, int b) {
    tree[h].a = (ll)tree[h].a*a%mod;
    tree[h].b = ((ll)tree[h].b*a + b) % mod;
    tree[h].s = ((ll)tree[h].s*a + b) % mod;
}
void update(int h, int l, int r, int gl, int gr, int a, int b) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) f(h, a, b);
    else {
        f(h * 2 + 1, tree[h].a, tree[h].b);
        f(h * 2 + 2, tree[h].a, tree[h].b);
        tree[h].a = 1;
        tree[h].b = 0;
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, a, b);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, a, b);
        tree[h].s = ((ll)(tree[h * 2 + 1].s + tree[h * 2 + 2].s)*tree[h].a + tree[h].b) % mod;
    }
}
int query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 0;
    if (gl <= l&&r <= gr) return tree[h].s;
    return (query(h * 2 + 1, l, (l + r) / 2, gl, gr) + query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr)) % mod;
}
int main() {
    scanf("%d%d", &n, &m);
    idx[sz++] = n;
    for (int i = 0; i < m; i++) scanf("%d%d", &p[i].first, &p[i].second), idx[sz++] = p[i].second;
    sort(p, p + m);
    sort(idx, idx + sz);
    sz = unique(idx, idx + sz) - idx;
    update(0, 0, sz - 1, 0, 0, 1, 1);
    for (int i = 0; i < m; i++) {
        int l = lower_bound(idx, idx + sz, p[i].first - 1) - idx,
            r = lower_bound(idx, idx + sz, p[i].second) - idx;
        update(0, 0, sz - 1, r, r, 1, query(0, 0, sz - 1, l, r));
        update(0, 0, sz - 1, r + 1, sz - 1, 2, 0);
    }
    printf("%d", query(0, 0, sz - 1, sz - 1, sz - 1));
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'int main()':
rail.cpp:36:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
rail.cpp:38:98: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < m; i++) scanf("%d%d", &p[i].first, &p[i].second), idx[sz++] = p[i].second;
                                                                                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...