100pts MLE 求助

y_kx_b @ 2023-10-27 10:35:59

by y_kx_b @ 2023-10-27 10:36:22

完整 code：

// Problem: P3740 [HAOI2014] 贴海报
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3740
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: P2391 白雪皑皑
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// command line option: 
// -std=c++14 -Wall -Wextra -Wshadow -Dlocal -Wl,-stack=114514191 -fno-ms-extensions -Wno-format 
#include<bits/stdc++.h>
#define gc getchar
#define x first
#define y second
#define eb emplace_back
#define em emplace
#define rep(i, x, y) for(auto i = (x); i <= (y); i++)
#define all(x) (x).begin(), (x).end()
using std::min; using std::max;
typedef long long ll; typedef unsigned long long ull;
// https://www.luogu.com.cn/discuss/522581 About "const"
ll read() {
    ll x = 0; bool fh = 0; char ch = gc();
    while (!isdigit(ch)) {
        fh |= ch == '-';
        if (ch < 10) exit(9); 
        ch = gc();
    }
    while (isdigit(ch))
        x = x * 10 + (ch ^ 48), ch = gc();
    return fh ? -x : x;
}
namespace myspace {
    #ifdef local
    template<typename Typ1> void debug(Typ1 arg) {std::cerr << arg << "\n";}
    template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {
        std::cerr << arg << " ", debug(args...);
    }
    template<typename InputIt> void debug(InputIt first, InputIt last) {
        for(; first != last; first++) std::cerr << *first << " ";
        std::cerr << std::endl;
    }
    #endif
    int writeln(ll arg) {return printf("%lld\n", arg);}
    template<typename ...Typ2> int writeln(ll arg, Typ2 ...args) {
        return printf("%lld ", arg), writeln(args...);
    }
    template<typename InputIt> int writeln(InputIt first, InputIt last) {
        if(first == last) return 0;
        printf("%lld", (ll)*(first++));
        for(; first != last; first++) printf(" %lld", (ll)*first);
        return puts("");
    }
    typedef std::pair<int, int> pii;
    const char YES[] = "YES", NO[] = "NO";
    // const char YES[] = "Yes", NO[] = "No";
    // #define infinite_testcase
    // #define multiple_testcase
    // #define output_Yes_No
    constexpr int DUST = 327, N = 11459810;
    struct DSU {//find(x) 表示 x 右边第一个没被染过的点
        int fa[N];
        void init(const int &n) {
            for(int i = 1; i <= n; i++) fa[i] = i;
        }
        int find(const int &x) {return fa[x] == x ? x : (fa[x] = find(fa[x]));}
        void merge(const int &u, const int &v) {
            int r1 = find(u), r2 = find(v);
            if(r1 == r2) {
                return;
            }
            // if(siz[r1] > siz[r2]) std::swap(r1, r2);
            fa[r1] = r2;
        }
        bool check(const int &u, const int &v) {return find(u) == find(v);}
    }dsu;
    pii p[1145];
    bool major(int Case = 1) {
        int n = read(), m = read();
        dsu.init(/*n*/n + 1);
        rep(i, 1, m) p[i].x = read(), p[i].y = read();
        int ans = 0;
        for(int i = m; i; i--) {
            int l = p[i].x, r = p[i].y;
            bool flag = 0;
            for(int i = dsu.find(l); i <= r; i = dsu.find(++i))
                flag = 1, dsu.merge(i, i + 1);
            ans += flag;
        }
        writeln(ans);
        return Case ^= Case ^ Case;
    }
    void initial_function(signed argc, char **argv) {
        **argv = argc; /*
        you won't give up no matter what happens, will you ?
        independently solved: 0
        code time:  >> 10:27
        ---
        草这两题是真一模一样啊，不说我还不知道（
        */
    }
}
using myspace::DUST;
signed main(signed argc, char **argv) {
    myspace::initial_function(argc, argv);
    int Case = 1, Maxcase = 1;
    for(
#ifdef multiple_testcase
        Maxcase = read()
#endif
                        ;
#ifndef infinite_testcase
                          Case <= Maxcase
#endif
                                         ; Case++)
#ifdef output_Yes_No
        puts(myspace::major(Case) ? YES : NO);
#else
        myspace::major(Case);
#endif
    return DUST ^ 0x147;
}

by y_kx_b @ 2023-10-27 10:41:17

upd：还真是递归空间太大了，手写栈之后就 80MB 过了 qwq

递归时间常数大，原来空间常数也这么大吗