Submission #20513

#	Time	Username	Problem	Language	Result	Execution time	Memory
20513		CYI (#35)	초음속철도 (OJUZ11_rail)	C++14	100 / 100	546 ms	12836 KiB

rail

#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;
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 = (tree[h * 2 + 1].s + tree[h * 2 + 2].s) % 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 (((ll)query(h * 2 + 1, l, (l + r) / 2, gl, gr) + query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr))*tree[h].a+tree[h].b) % mod;
}
int main() {
    scanf("%d%d", &n, &m);
    idx[sz++] = 1;
    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) - idx,
            r = lower_bound(idx, idx + sz, p[i].second) - idx;
        int t = query(0, 0, sz - 1, l, r);
        update(0, 0, sz - 1, r, r, 1, t);
        update(0, 0, sz - 1, r + 1, sz - 1, 2, 0);
    }
    printf("%d", query(0, 0, sz - 1, sz - 1, sz - 1));
    return 0;
}

Compilation message (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:39: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;
                                                                                                  ^

• Subtask 1: 10 / 10
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30