P6619 [省选联考 2020 A/B 卷] 冰火战士
  • Code

    #include<bits/stdc++.h>
    #define cint const int&
    #define lowbit(i) (i&-i)
    #define pii pair<int,int>
    using namespace std;
    const int maxn = 5e6;
    char opt;
    int j,m, n, vals[maxn], fire[maxn], ice[maxn], dtfire;
    struct {
        char t;
        int x, y;
    }ev[maxn];
    inline void addice(cint x, cint v) {
        for (auto i = x; i <= n; i += lowbit(i)) ice[i] += v;
    }
    inline void addfire(cint x, cint v) {
        dtfire += v;
        for (auto i = x + 1; i <= n; i += lowbit(i)) fire[i] -= v;
    }
    inline int get(cint pos) {
        int si = 0, sf = dtfire;
        for (int i = pos; i; i -= lowbit(i))
            si += ice[i], sf += fire[i];
        return min(si, sf);
    }
    inline pii find1() {
        int pos = 0, si = 0, sf = dtfire;
        for (int p = 20; p >= 0; --p) {
            int nxtpos = pos + (1 << p);
            if (nxtpos > n) continue;
            if (si + ice[nxtpos] <= sf + fire[nxtpos]) si += ice[nxtpos], sf += fire[pos = nxtpos];
        }
        return { min(sf,si), pos };
    }
    inline pii find2(cint gmin) {
        int pos = 0, si = 0, sf = dtfire;
        for (int p = 20; p >= 0; --p) {
            int nxtpos = pos + (1 << p);
            if (nxtpos > n) continue;
            if (si + ice[nxtpos] <= sf + fire[nxtpos]) si += ice[nxtpos], sf += fire[pos = nxtpos];
            else
                if (sf + fire[nxtpos] == gmin)
                    si += ice[nxtpos], sf += fire[pos = nxtpos];
        }
        return { gmin,pos };
    }
    int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            cin >> opt;
            if (opt == '1') {
                cin >> ev[i].t >> ev[i].x >> ev[i].y;
                vals[++n] = ev[i].x;
            }
            else {
                cin >> j;
                ev[i].t = ev[j].t;
                ev[i].x = ev[j].x;
                ev[i].y = -ev[j].y;
            }
        }
        sort(vals + 1, vals + n + 1);
        n = unique(vals + 1, vals + n + 1) - (vals + 1);
        for (int i = 1; i <= m; ++i)
            ev[i].x = lower_bound(vals + 1, vals + n + 1, ev[i].x) - vals;
        for (int i = 1; i <= m; ++i) {
            if (ev[i].t == '0')
                addice(ev[i].x, ev[i].y);
            else
                addfire(ev[i].x, ev[i].y);
            auto p1 = find1();
            auto p2 = find2(get(p1.second + 1));
            p1 = max(p1, p2);
            if (p1.first == 0)
                cout << "Peace\n";
            else
                cout << vals[p1.second] << ' ' << p1.first * 2 << '\n';
        }
    }
    
  • 树状数组是二分结构

    • 他比线段树快
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇