首页 > 其他分享 >【新题】$\rm Lg$月赛 $P8476$ 「惊蛰」

【新题】$\rm Lg$月赛 $P8476$ 「惊蛰」

时间：2022-08-15 19:49:40浏览次数：51  
标签：月赛 ch return tag1 tag2 Lg int 新题 lsp

「你曾在名为弱小的深渊中，曾经看到过什么。」

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

long long cal[N] = {0};

namespace OLD_CODE {
    typedef long long LL;

    int n, a[N], Num;
    int b[N], m;

    vector <LL> f[N];
    LL ans = 1e17;

    inline int Calc(int x, int y) {
        return x >= y ? x - y : Num;
    }

    void dfs(int x, int y, LL cost) {
        if(x > n) {
            ans = min(ans, cost);
            return;
        }
        if(f[x][y] <= cost) return;
        f[x][y] = cost;
        for(int i = y; i; --i) {
            dfs(x + 1, i, cost + Calc(b[i], b[a[x]]));
        }
    }

    namespace SUBTASK4 {
        inline void solve() {
            LL ret = 1LL * n * Num;
            ans = min(ans, ret);
            for(int i = 1; i <= n; ++i) {
                ret -= Num;
                ret += 1LL * (i - 1) * (a[i] - a[i - 1]);
                ans = min(ans, ret);
            }
            cout << ans;
        }
    }

    int flg = 1;

    signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("Ans.txt", "w", stdout);
    #endif
        scanf("%d %d", &n, &Num);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i), b[i] = a[i];
            if(i > 1 && a[i] < a[i - 1]) flg = 0;
        }

        if(Num == 0) return printf("0") & 0;
        if(flg) {
            SUBTASK4::solve();
            return 0;
        }

        sort(b + 1, b + n + 1);
        m = unique(b + 1, b + n + 1) - b - 1;
        for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        //for(int i = 1; i <= n + 5; ++i) f[i].reserve(m + 5);
        for(int j = 1; j <= m + 5; ++j) f[0].push_back(0);
        for(int i = 1; i <= n + 1; ++i)
            for(int j = 1; j <= m + 5; ++j) f[i].push_back(0x3f3f3f3f3f3f3f3f);

        //cout << m << endl;
        //for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
        //puts("");
        //for(int i = 1; i <= m; ++i) cout << b[i] << ' ';
        //puts("");
        //cout << f[1][1];
        //return 0;

        //for(int i = m; i; --i)
    //     dfs(1, i, 0);

        for(int i = 1; i <= n; ++i) {
            LL mn = 1e18;
            for(int j = m; j; --j) {
                mn = min(mn, f[i - 1][j]);
                f[i][j] = min(f[i][j], mn + 1LL * Calc(b[j], b[a[i]]));
            }
        }

        for(int i = 1; i <= m; ++i) 
            ans = min(ans, f[n][i]);
        
        cout << ans;
        return 0;
    }
}

namespace STD_SOL_CODE {
    typedef long long LL;
    typedef unsigned long long ULL;

    template <typename T> inline T read() {
        register T x = 0; register int w = 0, ch = getchar();
        for(; !isdigit(ch); ch = getchar()) w |= ch == 45;
        for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
        return w ? -x : x;
    }

    int n, k, a[N];
    int b[N], id[N];

    struct T {
        LL val, tag1, tag2;
        int fl;
    }t[N << 2];
    #define lsp p << 1
    #define rsp p << 1 | 1
    #define mid (l + r >> 1)

    inline void pushfl(int p) {
        if(!t[p].fl) return;
        t[lsp].val = t[rsp].val = t[p].val;
        t[lsp].tag1 = t[rsp].tag1 = t[lsp].tag2 = t[rsp].tag2 = 0;
        t[lsp].fl = t[rsp].fl = 1;
        t[p].fl = 0;
    }

    inline void pushup(int p) {
        t[p].val = min(t[lsp].val, t[rsp].val);
    }

    inline void pushdown(int p, int Mid, int r) {
        pushfl(p), pushfl(lsp), pushfl(rsp);
        if(t[p].tag1) {
            t[lsp].val += t[p].tag1; t[lsp].tag1 += t[p].tag1;
            t[rsp].val += t[p].tag1; t[rsp].tag1 += t[p].tag1;
            t[p].tag1 = 0;
        }
        if(t[p].tag2) {
            t[lsp].tag2 += b[Mid] * t[p].tag2; t[lsp].tag2 += t[p].tag2;
            t[rsp].tag2 += b[Mid] * t[p].tag2; t[rsp].tag2 += t[p].tag2;
        }
    }

    LL Val;

    void update(int p, int l, int r, int x, LL v1, LL v2) {
        if(l != r) pushdown(p, mid, r);
        if(r <= x) {
            pushfl(p);
            t[p].val += v1, t[p].tag1 += v1;
            t[p].val += b[r], ++t[p].tag2;
            if(r == x) Val = t[p].val;
            return;
        }
        if(l > x) {
            pushfl(p);
            t[p].val += v2, t[p].tag1 += v2;
            return;
        }
        update(lsp, l, mid, x, v1, v2);
        update(rsp, mid + 1, r, x, v1, v2);
        pushup(p);
    }

    int modify(int p, int l, int r, int x, LL v) {
        return 0;
    }
}

namespace TRIAL {
    typedef long long LL;

    int n, a[N], Num;
    int b[N], m;

    vector <LL> f[N];
    LL ans = 1e17;

    int tmp[N];
    LL ret[N];

    inline int Calc(int x, int y) {
        return x >= y ? x - y : Num;
    }

    int flg = 1;

    signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("Ans.txt", "w", stdout);
    #endif
        scanf("%d %d", &n, &Num);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i), b[i] = a[i];
            if(i > 1 && a[i] < a[i - 1]) flg = 0;
        }

        if(Num == 0) return printf("0") & 0;
        if(flg) {
            //SUBTASK4::solve();
            return 0;
        }

        sort(b + 1, b + n + 1);
        //memcpy(tmp, b, sizeof tmp);
        m = unique(b + 1, b + n + 1) - b - 1;
        for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        //for(int i = 1; i <= n + 5; ++i) f[i].reserve(m + 5);
        for(int j = 1; j <= m + 5; ++j) f[0].push_back(0);
        for(int i = 1; i <= n + 1; ++i)
            for(int j = 1; j <= m + 5; ++j) f[i].push_back(0x3f3f3f3f3f3f3f3f);

        for(int i = 1; i <= n; ++i) {
            LL mn = 1e18;
            for(int j = m; j; --j) {
                mn = min(mn, f[i - 1][j]);
                f[i][j] = min(f[i][j], mn + 1LL * Calc(b[j], b[a[i]]));
            }
        }

        for(int i = 1; i <= m; ++i) 
            ans = min(ans, f[n][i]);
        
        cout << ans << endl;

        for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
        cout << endl;
        for(int i = 1; i <= m; ++i) cout << b[i] << ' ';
        cout << endl;

        //int tp = 0;
        for(int i = 1; i <= n; ++i) tmp[i] = b[a[i]];
        //for(int i = 1; i <= n; ++i) tmp[i] = b[i];
        sort(tmp + 1, tmp + n + 1);

        for(int i = 1; i <= n; ++i) ret[i] = ret[i - 1] + tmp[i];
        for(int i = 1; i <= n; ++i) cout << tmp[i] << ' ';
        cout << endl;

        LL t = 0x7f7f7f7f7f7f7f;
        int pos = 0;

        cout << endl;
        for(int i = 1; i <= n; ++i) cout << (cal[i] = Calc(b[5], b[a[i]])) << ' ';
        cout << endl;
        sort(cal + 1, cal + n + 1);
        for(int i = 1; i <= n; ++i) cout << cal[i] << ' ';
        cout << endl;

        for(int j = 1; j <= m; ++j) {
            int p = lower_bound(tmp + 1, tmp + n + 1, b[j]) - tmp;
            cout << "p = " << p << endl;
            LL res = 1LL * p * b[j] - ret[p] + (n - p) * Num;
            if(t > res) t = res, pos = j;
        }

        cout << t << ' ' << pos << endl;

        return 0;
    }
    signed main_() {
        //OLD_CODE::main();
        stack <long long> st;
        TRIAL::main();
        cout << endl;
        //using namespace OLD_CODE;
        using namespace TRIAL;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                printf("- %2d ", Calc(b[j], b[a[i]]));
            }
            cout << endl;
            LL Mn = 1e17;
            for(int j = m; j; --j) {
                Mn = min(Mn, f[i][j]);
                st.push(Mn);
            }
            while(!st.empty()) {
                printf("%4d ", st.top());
                st.pop();
            }
            cout << "<<" << endl;
            for(int j = 1; j <= m; ++j) {
                printf("%4d ", f[i][j]);
            }
            cout << "*" << endl;
        }
        return 0;
        //for(int i = 1; i <= n; ++i) ret[i] = ret[i - 1] + b[i];
    }
}

namespace FINAL_CODE {
    typedef long long LL;
    #define lsp p << 1
    #define rsp p << 1 | 1
    #undef mid
    #define Mid mid = (t[p].l + t[p].r >> 1)
    int n, C, a[N];
    vector <int> s;

    template <typename T> inline T read() {
        T x = 0; int w = 0, ch = getchar();
        for(; !isdigit(ch); ch = getchar()) w |= ch == 45;
        for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
        return w ? -x : x;
    }

    struct Node {
        int l, r, add, flag;
        LL val, minn = -1, del;
    }t[N << 2];

    inline void pushup(int p) { t[p].val = min(t[lsp].val, t[rsp].val); }
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if(l == r) return t[p].add = s[l - 1], void();
        int Mid; build(lsp, l, mid); build(rsp, mid + 1, r);
        //pushup(p);
        t[p].add = t[lsp].add;
    }
    inline void Fxadd(int p,  int v) { t[p].flag += v, t[p].val += 1LL * t[p].add * v; }
    inline void Fxmin(int p, LL v) { t[p].del = t[p].flag = 0, t[p].val = t[p].minn = v; }
    inline void Fxdel(int p, LL v) { t[p].del += v, t[p].val -= v; }
    inline void pushdown(int p) {
        if(~t[p].minn) Fxmin(lsp, t[p].minn), Fxmin(rsp, t[p].minn), t[p].minn = -1;
        if(t[p].flag) Fxadd(lsp, t[p].flag), Fxadd(rsp, t[p].flag), t[p].flag = 0;
        if(t[p].del) Fxdel(lsp, t[p].del), Fxdel(rsp, t[p].del), t[p].del = 0;
    }

    void modify(int p, int l, int r, int v) {
        if(l <= t[p].l && t[p].r <= r) return Fxadd(p, 1), Fxdel(p, v); pushdown(p);
        int Mid; if(l <= mid) modify(lsp, l, r, v); if(mid < r) modify(rsp, l, r, v); pushup(p);
    }

    void update(int p, int l, int r, int v) {
        if(l <= t[p].l && t[p].r <= r) return t[p].val += v, t[p].del -= v, void(); pushdown(p);
        int Mid; if(l <= mid) update(lsp, l, r, v); if(mid < r) update(rsp, l, r, v); pushup(p);
    }

    void change(int p, int l, int r, LL v) {
        if(l <= t[p].l && t[p].r <= r) {
            if(t[p].l == t[p].r) return t[p].val = min(t[p].val, v), void();
            pushdown(p);
            if(t[rsp].val <= v) return change(rsp, l, r, v);
            return Fxmin(rsp, v), change(lsp, l, r, v);
        }
        pushdown(p); int Mid;
        if(l <= mid) change(lsp, l, r, v); if(mid < r) change(rsp, l, r, v);
        pushup(p);
    }

    LL query(int p, int x) {
        if(t[p].l == t[p].r) return t[p].val;
        pushdown(p); int Mid;
        return x <= mid ? query(lsp, x) : query(rsp, x);
    }

    signed main() {
        n = read<int>(), C = read<int>();
        if(!C) return puts("0") & 0;
        for(int i = 1; i <= n; ++i) s.push_back(a[i] = read<int>());
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        build(1, 1, (int)s.size());

        for(int i = 1; i <= n; ++i) 
            a[i] = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;
        LL res;
        for(int i = 1; i <= n; ++i) {
            modify(1, a[i], (int)s.size(), s[a[i] - 1]);
            if(a[i] != 1) {
                update(1, 1, a[i] - 1, C);
                change(1, 1, a[i] - 1, res = query(1, a[i]));
            }
        }
        cout << t[1].val;
        return 0;
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    FINAL_CODE::main();
    return 0;
}

标签：月赛,ch,return,tag1,tag2,Lg,int,新题,lsp
From： https://www.cnblogs.com/Doge297778/p/16589406.html

相关文章

  • LGP8474题解
    很萌萌的数数题。考虑设\(dp[n]\)表示\(n\)的答案。考虑对于一个长度为\(n\)的排列，令排列的所有元素\(+1\)，然后塞一个\(1\)进去。容易发现，逆序对增加的数量和......
  • 8.14 洛谷月赛
    感觉没有tg难\(\rmLink\)目录\(T1\)\(T2\)\(T3\)（主打\(div2\)）\(T1\)这个\(T1\)是个神仙题，我甚至为它写了一个\(45pts\)的暴力分然后过去切了\(T2\)再回来看才......
  • 牛客小白月赛54 C School（思维）
    https://ac.nowcoder.com/acm/contest/38457/C爆时版本，想不明白D国的时间制度很奇怪，一天有h小时，一小时有m分。位于D国的校长给学生发放了校卡。这种校卡具......
  • 牛客小白月赛54 B.Gaming（差分）
    链接：https://ac.nowcoder.com/acm/contest/38457/B他玩的游戏共有n个挑战房间，和m个debuff。他非常强，只要不是带着所有的debuff，他都能打过boss获得胜利。进入第......
  • 牛客小白月赛54 D-Word（最短路/bfs）
    链接：https://ac.nowcoder.com/acm/contest/38457/D题目描述给你一个包含n个单词的单词表。你需要将单词s以如下操作转换成t。每次改变s的一个字母。你需要保证......
  • 【牛客小白月赛】54 C School
    链接https://ac.nowcoder.com/acm/contest/38457/C题意是说，给你n个形如a时b分c时d分的条件限制，表示不能选取，给出m个询问某个值是否可以选取思路1.可以把x时y分转化成......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99