답안 #24783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24783 2017-06-13T20:37:43 Z chpipis 사다리꼴 (balkan11_trapezoid) C++11
100 / 100
176 ms 17384 KB
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 1e5 + 5;
const int MOD = 30013;

struct side {
    int l, r, idx;
    bool right_end;
};

inline bool comp(const side &lhs, const side &rhs) {
    if (lhs.l == rhs.l) {
        if (lhs.r == rhs.r)
            return lhs.right_end < rhs.right_end;
        return lhs.r < rhs.r;
    }
    return lhs.l < rhs.l;
}

vector<side> seg;
vector<side> sec_seg;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[MAXN], cnt[MAXN];
vi cc;

inline bool comp_dp(const side &lhs, const side &rhs) {
    if (dp[lhs.idx] == dp[rhs.idx]) {
        if (lhs.l == rhs.l)
            return lhs.right_end < rhs.right_end;
        return lhs.l < rhs.l;
    }
    return dp[lhs.idx] < dp[rhs.idx];
}

int bit_max[MAXN * 2], bit_sum[MAXN * 2];

#define lsone(s) (s & (-s))

void add_max(int b, int val) {
    while (b < MAXN * 2) {
        bit_max[b] = max(bit_max[b], val);
        b += lsone(b);
    }
}

int ask_max(int b) {
    int res = 0;
    while (b > 0) {
        res = max(res, bit_max[b]);
        b -= lsone(b);
    }
    return res;
}

void add_sum(int b, int val) {
    b++;
    while (b < MAXN * 2) {
        bit_sum[b] = (bit_sum[b] + val) % MOD;
        b += lsone(b);
    }
}

int ask_sum(int b) {
    b++;
    int res = 0;
    while (b > 0) {
        res = (res + bit_sum[b]) % MOD;
        b -= lsone(b);
    }
    return res;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    cc.pb(0);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        cc.pb(c[i]);
        cc.pb(d[i]);
    }
    sort(all(cc));
    cc.resize(unique(all(cc)) - cc.begin());

    seg.reserve(2 * n + 1);

    seg.pb((side){0, 0, 0, true});
    for (int i = 1; i <= n; i++) {
        c[i] = lower_bound(all(cc), c[i]) - cc.begin();
        d[i] = lower_bound(all(cc), d[i]) - cc.begin();
        seg.pb((side){a[i], c[i], i, false});
        seg.pb((side){b[i], d[i], i, true});
    }
    seg.pb((side){(int)1e9 + 5, 2 * n + 5, n + 1, false});

    sort(all(seg), comp);

    vii vec;

    vec.pb(mp(0, 0));
    for (int i = 1; i < (int)seg.size(); i++) {
        auto it = seg[i];
        if (it.right_end) {
            add_max(it.r, dp[it.idx]);
        } else {
            dp[it.idx] = ask_max(it.r - 1) + 1;
        }
        vec.pb(mp(dp[it.idx], it.r));
    }

    sort(all(vec));

    cnt[0] = 1;

    //int last = 0;
    for (int i = 0, j = 0; i < (int)seg.size(); i++) {
        auto it = seg[i];
        if (it.right_end) {
            int pos = lower_bound(all(vec), mp(dp[it.idx], it.r)) - vec.begin();
            add_sum(pos, cnt[it.idx]);
        } else {
            int st = lower_bound(all(vec), mp(dp[it.idx] - 1, 0)) - vec.begin();
            int en = lower_bound(all(vec), mp(dp[it.idx] - 1, it.r)) - vec.begin();
            cnt[it.idx] = (ask_sum(en - 1) - ask_sum(st - 1) + MOD) % MOD;
        }
        /*j = i;
        while (j < (int)seg.size() && dp[seg[j].idx] == dp[seg[i].idx]) {
            auto it = seg[j];
            printf("processing %d, right_end? %d\n", it.idx, it.right_end);
            j++;
            if (it.right_end) continue;
            while (last < i && dp[seg[last].idx] < dp[it.idx] - 1) {
                if (seg[last].right_end)
                    add_sum(seg[last].r, -cnt[seg[last].idx]);
                last++;
            }
            cnt[it.idx] = ask_sum(it.r - 1);
            printf("last is %d\n", last);
        }
        j = i;
        while (j < (int)seg.size() && dp[seg[j].idx] == dp[seg[i].idx]) {
            auto it = seg[j];
            if (it.right_end)
                add_sum(it.r, cnt[it.idx]);
            j++;
        }*/
    }
#if 0
    for (int i = 0; i <= n + 1; i++) {
        printf("%d) dp: %d, cnt: %d\n", i, dp[i], cnt[i]);
    }
#endif
    printf("%d %d\n", dp[n + 1] - 1, cnt[n + 1]);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:167:21: warning: unused variable 'j' [-Wunused-variable]
     for (int i = 0, j = 0; i < (int)seg.size(); i++) {
                     ^
trapezoid.cpp:126:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:129:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
                                                         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5932 KB Output is correct
2 Correct 0 ms 5932 KB Output is correct
3 Correct 0 ms 6064 KB Output is correct
4 Correct 0 ms 6120 KB Output is correct
5 Correct 3 ms 6104 KB Output is correct
6 Correct 6 ms 6260 KB Output is correct
7 Correct 3 ms 6324 KB Output is correct
8 Correct 6 ms 6644 KB Output is correct
9 Correct 13 ms 7280 KB Output is correct
10 Correct 39 ms 8544 KB Output is correct
11 Correct 39 ms 8856 KB Output is correct
12 Correct 83 ms 11700 KB Output is correct
13 Correct 109 ms 12324 KB Output is correct
14 Correct 126 ms 15508 KB Output is correct
15 Correct 143 ms 15820 KB Output is correct
16 Correct 169 ms 16136 KB Output is correct
17 Correct 146 ms 16448 KB Output is correct
18 Correct 133 ms 16760 KB Output is correct
19 Correct 156 ms 17072 KB Output is correct
20 Correct 176 ms 17384 KB Output is correct