QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#880885#8035. Call Me Call Megsn531WA 93ms936800kbC++264.4kb2025-02-03 22:32:112025-02-03 22:32:12

Judging History

This is the latest submission verdict.

  • [2025-02-06 18:39:16]
  • hack成功,自动添加数据
  • (/hack/1529)
  • [2025-02-03 22:32:12]
  • Judged
  • Verdict: WA
  • Time: 93ms
  • Memory: 936800kb
  • [2025-02-03 22:32:11]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

//18

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair
#define tt T[dep]
bool Mst;

const int maxn = 4e5 + 5, inf = 1e9;

int n;
struct node{
    int l, r, k;
}a[maxn];

struct SGT{

    pii t[maxn << 2]; int tg[maxn << 2], rc[maxn];
    set<pii> q[maxn], qr[maxn];
    vector<pii> D;

    #define ls (x << 1)
    #define rs (x << 1 | 1)

    inline void up(int x){ t[x] = min(t[ls], t[rs]); }
    inline void mo(int x, int v){ t[x].fi += v; tg[x] += v; }
    inline void dw(int x){
        mo(ls, tg[x]), mo(rs, tg[x]); tg[x] = 0;
    }

    inline void build(int x, int l, int r){
        if(l == r) return t[x] = mkp((*q[l].begin()).fi, l), tg[x] = 0, rc[l] = x, void();
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        up(x);
    }
    inline void init(){
        rep(i, 1, n) q[i].insert(mkp(inf, inf)), qr[i].insert(mkp(inf, inf));
        build(1, 1, n);
    }
    inline void updtr(int x, int l, int r, int L, int R, int v){
        if(l >= L and r <= R) return mo(x, v), void();
        int mid = l + r >> 1; dw(x);
        if(L <= mid) updtr(ls, l, mid, L, R, v); if(R > mid) updtr(rs, mid + 1, r, L, R, v);
        up(x);
    }
    inline void updtp(int x, int l, int r, int p, int id, int val){
        if(l == r){
            int nat = (*q[l].begin()).fi - t[x].fi;
            pii dmd = *qr[l].lower_bound(mkp(id, -inf));
            qr[l].erase(dmd), q[l].erase(mkp(dmd.se, dmd.fi));
            if(val)
                qr[l].insert(mkp(id, val)), q[l].insert(mkp(val, id));
            t[x].fi = (*q[l].begin()).fi - nat;
            return;
        }
        int mid = l + r >> 1; dw(x);
        if(p <= mid) updtp(ls, l, mid, p, id, val);
        else updtp(rs, mid + 1, r, p, id, val);
        up(x);
    }
}T[18];

inline void Solve(int dep, int L, int R, vector<int> &S){
    if(L > R or !S.size()) return;
    if(L == R){
        tt.D.push_back(mkp(L, R));
        for(int i : S) 
            tt.q[L].insert(mkp((a[i].k + 1) / 2, i)),
            tt.qr[L].insert(mkp(i, (a[i].k + 1) / 2));
        return;
    }
    int mid = L + R >> 1;
    tt.D.push_back(mkp(L, R));
    
    vector<int> Ls, Rs;
    for(int i : S){
        if(a[i].r <= mid){ Ls.push_back(i); continue; }
        if(a[i].l > mid){ Rs.push_back(i); continue; }
        
        tt.q[a[i].l].insert(mkp((a[i].k + 1) / 2, i));
        tt.qr[a[i].l].insert(mkp(i, (a[i].k + 1) / 2));
        tt.q[a[i].r].insert(mkp((a[i].k + 1) / 2, i));
        tt.qr[a[i].r].insert(mkp(i, (a[i].k + 1) / 2));
    }
    Solve(dep + 1, L, mid, Ls), Solve(dep + 1, mid + 1, R, Rs);
}

int Ans, inq[30];

inline void calc(){
    int lmt = 0; while(T[lmt + 1].D.size()) ++lmt;
    queue<int> q;
    rep(i, 1, lmt) if(T[i].t[1].fi <= 0) q.push(i), inq[i] = 1;
    while(q.size()){
        int dep = q.front(); q.pop(); inq[dep] = 0;
        int pos = tt.t[1].se;//l or r
        int id = (*tt.q[pos].begin()).se;
        int l = a[id].l, r = a[id].r, k = a[id].k;

        int natl = (*tt.q[l].begin()).fi - tt.t[tt.rc[l]].fi;
        int natr = (*tt.q[r].begin()).fi - tt.t[tt.rc[r]].fi;
        k = max(0, k - natl - natr); k = (k + 1) / 2;
        tt.updtp(1, 1, n, l, id, k), tt.updtp(1, 1, n, r, id, k);

        if(!k){
            ++Ans;
            rep(i, 1, lmt){
                pii d = *prev(upper_bound(T[i].D.begin(), T[i].D.end(), mkp(id, id)));
                if(!(d.fi <= id and d.se >= id)) continue;
                int mid = d.fi + d.se >> 1;
                if(id > mid) T[i].updtr(1, 1, n, id, d.se, -1);//注意贡献不同!!!!
                else T[i].updtr(1, 1, n, d.fi, id, -1);
                if(T[i].t[1].fi <= 0 and !inq[i])
                    inq[i] = 1, q.push(i);
            }
        }
    }
}

bool Med;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    // fprintf(stderr, "%.2lfMB\n", abs(&Mst - &Med) / 1024. / 1024.);

    cin >> n;
    rep(i, 1, n) cin >> a[i].l >> a[i].r >> a[i].k;

    vector<int> tmp; rep(i, 1, n) tmp.push_back(i);
    Solve(1, 1, n, tmp);
    rep(i, 1, 17) T[i].init(), sort(T[i].D.begin(), T[i].D.end());

    calc();
    cout << Ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 93ms
memory: 936800kb

input:

3
2 3 2
2 3 1
2 2 0

output:

1

result:

wrong answer 1st numbers differ - expected: '3', found: '1'