cout的输出呢???
查看原帖
cout的输出呢???
655351
evening_maple楼主2022/8/9 02:38

why?在洛谷在线运行以下

7 0
I 8
I 10
I 12
S 10
F 1
S 2
F 1

代码的时候输出了个0??? 然后把cout改成了write()函数就过了??? 所以cout是有bug吗QAQ

//#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define bug(x) cout << #x << " = " << x << '\n';

using namespace std;
#define ll int
#define dd double
#define endl '\n'
#define pll pair<ll,ll>

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline bool read(ll& x) {
    x = 0;
    char c = getchar();
    if (c == EOF)return false;
    else if (c == '}')return 0;
    while (c > '9' || c < '0')c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return true;
}

template<class T>void unwrite(T x) {
    if (x > 9) unwrite(x / 10);
    putchar(x % 10 + '0');
}

template<class T>inline void write(T x) {
    x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
}

template<class T>inline void write(T x, char&& c) {
    x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
    putchar(c);
}

//void solve()
//{
//    ll dp[1003], inf = -1, len = 10, a[100];
//
//    for (int i = 0; i < len; ++i)a[i] = read();
//
//    fill(dp, dp + len, inf);
//
//    for (int i = 0; i < len; ++i)
//        *lower_bound(dp, dp + len, a[i]) = a[i];
//    
//    for (int i = 0; i < len; ++i)write(dp[i], ' ');
//
//    putchar('\n');
//
//    write(lower_bound(dp, dp + len, inf) - dp, '\n');
//}
//
//priority_queue<ll, vector<ll>, greater<ll>> B;



//priority_queue<ll, vector<ll>, greater<ll>> xiao;
//priority_queue<ll> da;

inline ll max(ll a, ll b) {
    return a > b ? a : b;
}

inline ll min(ll a, ll b) {
    return a < b ? a : b;
}

ll pow(ll di, ll zhi, ll mod = 1e9 + 7) {
    ll ans = 1;

    for (di %= mod; zhi != 0; zhi >>= 1) {
        if (zhi & 1)ans = ans * di % mod;
        di = di * di % mod;
    }
    return ans;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);

    for (ll c = 0; b != 0; b = c % b)c = a, a = b;

    return a;
}

// a * x + b * y = gcd(a, b)
ll Exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = Exgcd(b, a % b, x, y), t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

// ------------------------------------------------
const ll inf = 1e16 + 7ll, mod = 1e9 + 7ll, N = 1e5 + 3;

/*
权值线段树 + 离散化 + 双向函数映射 
*/

struct node {
    ll l = 0, r = 0, v = inf, ge = 0, kai = 0;
};

ll n, m, i, j, k, kk, y, len, llen, add, kai;

struct nnnn {
    char cc; ll k;
}A[300005];

map<ll, ll>B;
ll C[300005];

vector<node>D;

void out() {
    cout << "\ni l r g v k\n";

    for (ll i = 1; i < len << 1; ++i)
        cout << i << ' ' << D[i].l << ' ' << D[i].r << ' ' << D[i].ge << ' ' << D[i].v << ' ' << D[i].kai << endl;
}

void bulid() {
    for (len = llen << 1; len != (-len & len); len -= -len & len); D.resize(len << 1);

    for (i = 0; i < len; ++i)D[i + len].l = D[i + len].r = D[i + len].v = i + 1;
    
    for (i = len - 1; i > 0; --i)
        D[i].l = D[i << 1].l, D[i].r = D[i << 1 | 1].r,
        D[i].v = D[i << 1 | 1].v;

    //out();
}

inline void spread(ll k) {
    if (D[k].kai) {

        D[k].ge = D[k].kai = 0;
        if (k < len)
            D[k << 1].kai = D[k << 1 | 1].kai = 1;
    }
}

void cz1() {
    for (j = 1; j < len;) {
        spread(j);

        ++D[j].ge;
        j <<= 1;
        
        if (D[j].v < kk)j |= 1;
    }

    if (D[j].kai)D[j].ge = 1, D[j].kai = 0;
    else ++D[j].ge;
}

//[1, y)
ll cz3(ll k) {
    //bug(k);

    if (D[k].l >= y || D[k].kai)return 0;
    else if (D[k].r < y)
        return D[k].kai = 1, D[k].ge;
    
    else{
        ll ans = cz3(k << 1) + cz3(k << 1 | 1);
        D[k].ge -= ans;
        return ans;
    }
}

void cz4(ll k) {
    //bug("++++++++++++++++++++++++");

    while (k < len) {
        k <<= 1;

        spread(k);
        spread(k | 1);

        if (D[k | 1].ge >= kk)k |= 1;
        else kk -= D[k | 1].ge;
    }

    cout << C[k - len + 1] + add << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    for (n = read(), m = read(); i < n; ++i) {
        cin >> A[i].cc >> A[i].k;

        if (A[i].cc == 'A')add += A[i].k;
        else if (A[i].cc == 'S')add -= A[i].k, B[m - add] = 0;
        else if (A[i].cc == 'I')A[i].k -= add, B[A[i].k] = 0;
    }

    for (auto& x : B)x.second = ++llen, C[llen] = x.first;

    //for (i = 1; i <= llen; ++i)cout << C[i] << ' '; cout << endl;

    bulid(); add = 0;

    for (i = 0; i < n; ++i) {
        //cout << A[i].cc << ' ' << A[i].k << endl;
        switch (A[i].cc)
        {
        case 'I':
            if (A[i].k + add >= m) kk = B[A[i].k], cz1();
            break;

        case 'A':
            add += A[i].k;
            break;

        case 'S':
            add -= A[i].k;
            y = B[m - add];

            kai += cz3(1);
            break;

        case 'F':
            kk = A[i].k;
            if (D[1].ge < kk)cout << -1 << endl;
            else cz4(1);
            break;

        default:
            break;
        }
        //out();
    }

    cout << kai << endl;
}

inline void out2(double ans) {
    printf("%.2lf", ans);
}

/*
11 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
I 50
I 0

9 10
I 30
I 40
I 50
S 35
F 2
A 35
I 20
F 2
F 1
--
-1 20 50 2

11 10
I 30
I 30
I 30
S 20
I 20
F 1
F 2
A 10
S 15
F 2
F 1
--
20 10 -1 15 3

5 5
A 10
A 20
I 3
I 5
F 1
--
5 0

5 20
A 10000000
A 10000000
I 5
I 4
F 1
--
-1 0

10 10
I 50
I 100
I 70
S 40
A 20
F 2
I 5
A 10
F 3
S 10000
--
50 40 3

5 3
I 2
I 1
I 3
A 10
F 1
--
13 0

7 0
I 8
I 10
I 12
S 10
F 1
S 2
F 1
--
2 0 2

*/
2022/8/9 02:38
加载中...