Submission #164039

#	Time	Username	Problem	Language	Result	Execution time	Memory
164039		xtalxlr	초음속철도 (OJUZ11_rail)	C++17	100 / 100	914 ms	133044 KiB

rail

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

typedef pair<int, int> pii;
typedef long long ll;
const ll mod = 1000000007LL;
const int N = 2000050;
ll mul[4*N], tot[4*N];

void init() {
    for (int i = 0; i < 4*N; i++) {
        mul[i] = 1LL;
        tot[i] = 0LL;
    }
}

void propagate(int i, int st, int ed) {
    tot[i] = (tot[i] * mul[i]) % mod;
    int li = 2*i+1, ri = 2*i+2;
    if (ed - st > 1) {
        mul[li] = mul[li] * mul[i] % mod;
        mul[ri] = mul[ri] * mul[i] % mod;
    }
    mul[i] = 1LL;
}

void q_mul(ll val, int q_st, int q_ed, int i=0, int st=0, int ed=N) {
    if (q_st == st && q_ed == ed) {
        mul[i] = mul[i] * val % mod;
    } else {
        propagate(i, st, ed);
        int md = st + (ed - st) / 2;
        if (q_st < md)
            q_mul(val, q_st, min(q_ed, md), 2*i+1, st, md);
        propagate(2*i+1, st, md);
        if (md < q_ed)
            q_mul(val, max(q_st, md), q_ed, 2*i+2, md, ed);
        propagate(2*i+2, md, ed);
        tot[i] = (tot[2*i+1] + tot[2*i+2]) % mod;
    }
}

void q_add(ll val, int qi, int i=0, int st=0, int ed=N) {
    if (st == qi && ed == qi + 1) {
        propagate(i, st, ed);
        tot[i] = (tot[i] + val) % mod;
    } else {
        propagate(i, st, ed);
        int md = st + (ed - st) / 2;
        if (qi < md)
            q_add(val, qi, 2*i+1, st, md);
        else 
            q_add(val, qi, 2*i+2, md, ed);
        tot[i] = (tot[2*i+1] + tot[2*i+2]) % mod;
    }
}

ll q_sum(int q_st, int q_ed, int i=0, int st=0, int ed=N) {
    if (q_st == st && q_ed == ed) {
        propagate(i, st, ed);
        return tot[i];
    } else {
        propagate(i, st, ed);
        ll res = 0LL;
        int md = st + (ed - st) / 2;
        if (q_st < md)
            res += q_sum(q_st, min(q_ed, md), 2*i+1, st, md);
        if (md < q_ed)
            res += q_sum(max(q_st, md), q_ed, 2*i+2, md, ed);
        return res;
    }
}

int n;
vector< pair<int, int> > p;

int main() {
    int last;
    scanf("%d %d", &last, &n);
    vector<int> vals;
    vals.push_back(1);
    vals.push_back(last);
    for (int i = 0; i < n; i++) {
        int s, e;
        scanf("%d %d", &s, &e);
        vals.push_back(s);
        vals.push_back(e);
        p.emplace_back(s, e);
    }
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    for (auto &pr : p) {
        pr.first = lower_bound(vals.begin(), vals.end(), pr.first) - vals.begin();
        pr.second = lower_bound(vals.begin(), vals.end(), pr.second) - vals.begin();
    }
    sort(p.begin(), p.end(), [](const pii &p1, const pii &p2) {
            return p1.second < p2.second;
            });

    init();
    q_add(1, 0);
    for (auto &pr : p) {
        int st = pr.first;
        int ed = pr.second;
        // printf("%d %d\n", st, ed);
        if (st > 0)
            q_mul(2LL, 0, st);
        ll s = q_sum(st, ed + 1);
        // printf("%lld\n", s);
        q_add(s, ed); // q_add(ed, s);
        /*
        for (int i = 0; i < 5; i++)
            printf("%lld ", q_sum(i, i + 1));
        printf("\n");
        */
    }

    int lval = int(vals.size()) - 1;
    // printf("%d\n", lval);
    printf("%lld\n", q_sum(lval, lval + 1));

    return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &last, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
rail.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &s, &e);
         ~~~~~^~~~~~~~~~~~~~~~~

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