QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164906#6733. Moniphant Sleepucup-team1209RE 12ms75540kbC++145.1kb2023-09-05 14:40:202023-09-05 14:40:21

Judging History

你现在查看的是测评时间为 2023-09-05 14:40:21 的历史记录

  • [2023-09-05 22:11:21]
  • 管理员手动重测本题所有提交记录
  • 测评结果:RE
  • 用时:6ms
  • 内存:74440kb
  • [2023-09-05 14:40:21]
  • 评测
  • 测评结果:0
  • 用时:12ms
  • 内存:75540kb
  • [2023-09-05 14:40:20]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;

cs int oo = 1e9 + 7; 

cs int N = 5e5 + 5; 

int n, q; 

int fix(int x) {
    if(x >= oo - 5) return oo; 
    return x; 
}

struct func {
    int v1, p, v2, vi; 
    func (int v1 = 0, int p = -1, int v2 = -1, int vi = oo) 
        : v1(v1), p(p), v2(v2), vi(vi) {}
    int operator () (int x) {
        if(x == oo) return vi;
        if(x <= p) return v1; 
        return fix(v2 + x - p); 
    }
    void operator += (cs int &x) {
        v1 += x; 
        v2 += x; 
        vi += x; 
        if(v1 < 0) {
            v1 = oo; 
        }
        if(v2 < -1) {
            p -= v2 + 1; 
            v2 = -1;
        }
        if(vi < 0) {
            vi = oo; 
        }
        v1 = fix(v1); 
        v2 = fix(v2); 
        vi = fix(vi);
        p = fix(p);
    }
    void trans() {
        if(v1 == oo) v1 = 0;
        if(vi == oo) vi = 0; 
    }
};

func operator + (cs func &a, cs func &b) {
    if(a.p == oo && b.p == oo) 
        return func(fix(a.v1 + b.v1), oo, 0, fix(a.vi + b.vi)); 
    if(a.p == oo) 
        return func(fix(a.v1 + b.v1), b.p, fix(a.v1 + b.v2), fix(a.vi + b.vi));
    if(b.p == oo)
        return func(fix(a.v1 + b.v1), a.p, fix(a.v2 + b.v1), fix(a.vi + b.vi));
    // cout << a.p << ' ' << a.v1 << ' ' << a.v2 << ' ' << a.vi << endl;
    // cout << b.p << ' ' << b.v1 << ' ' << b.v2 << ' ' << b.vi << endl;
    assert(0);
}

struct skip {
    func a, c; 
    int d; 
    skip (func a = func(0, oo, 0, 0), func c = func(0, -1, -1, oo), int d = 0) : a(a), c(c), d(d) {}
};

func F(func a, func b) {
    func c; 
    if(a.p == oo) {
        c = func (a.v1, oo, 0, a(b.vi));
        assert(c(oo) == a(b(oo)));
        return c; 
    }
    if(b.p == oo) {
        c = func (a(b.v1), oo, 0, a(b.vi)); 
        assert(c(oo) == a(b(oo)));
        return c;
    }
    // a(b(d)) 
    c.vi = a(b.vi);

    // [0, b.p] -> c = a(b.v1) 
    c.p = b.p; 
    c.v1 = a(b.v1);
    // cout << "Fdsafsfasdfas " << b.v1 << ' ' << a(b.v1) << endl;
    // [b.v2 + 1, a.p] -> c = a.v1 
    if(a.p > b.v2) {
        // b.p + 1 -> b.v2 + 1 
        c.p += a.p - b.v2; 
        c.v1 = a.v1; 
    }
    c.v2 = a(b(c.p + 1)) - 1;

    for(int i = 0; i <= 10; i++) 
        assert(c(i) == a(b(i))); 
    assert(c(oo) == a(b(oo)));

    return c; 
}

func flat (func x) {
    if(x.v1 == oo) x.v1 = 0; 
    if(x.vi == oo) x.vi = 0; 
    return x; 
}
#define mid ((l + r) >> 1)
skip t[N << 2];
bool add[N << 2]; 


void pbpb(int x, skip & c, int op) {
    if(op == 1) {
        c.c += 1;
        c.d += 1; 
    }
    if(op == 2) {
        c.c += -1; 
        c.d -= 1; 
    }
    if(op == 3) {
        c.c.trans();
    }
    if(op == 4) {
        c.a = c.a + flat(c.c); 
        c.c = F(func(0, oo, 0, oo), c.c); 
        add[x] = 1; 
    }
}

void put(int x, skip c, bool ad) {
    // d -> c (d) -> t[x] (c (d)) 
    if(ad) {
        t[x].a = t[x].a + flat(F(c.a, t[x].c));
        add[x] = 1; 
    }
    t[x].d += c.d; 
    t[x].c = F(c.c, t[x].c);
}

void down(int x) {
    put(x << 1, t[x], add[x]);
    put(x << 1 | 1, t[x], add[x]);
    add[x] = 0; 
    t[x] = skip();
}

void modify (int x, int l, int r, int L, int R, int op) {
    // cout << "modify " << x <<' ' << l << ' ' << r << ' ' << L << ' ' <<  R << endl;
    if(L <= l && r <= R) {
        pbpb(x, t[x], op);
        // cout << "modify "<< x << ' ' << l <<' ' << r << ' ' << endl;
        // cout << t[x].a.v1 << ' ' << t[x].a.p << ' ' << t[x].a.v2 << ' ' << t[x].a.vi << endl;
        // cout << t[x].c.v1 << ' ' << t[x].c.p << ' ' << t[x].c.v2 << ' ' << t[x].c.vi << endl;
        // cout << t[x].d << ' ' << t[x].a(oo) << endl;
        return;
    }
    down(x);
    if(L <= mid) modify(x << 1, l, mid, L, R, op);
    if(R > mid) modify(x << 1 | 1, mid + 1, r, L, R, op); 
}

int query(int x, int l, int r, int p) {
    if(l == r) {
        // cout << "query "<< l << endl;
        // cout << t[x].a.v1 << ' ' << t[x].a.p << ' ' << t[x].a.v2 << ' ' << t[x].a.vi << endl;
        // cout << t[x].c.v1 << ' ' << t[x].c.p << ' ' << t[x].c.v2 << ' ' << t[x].c.vi << endl;
        // cout << t[x].d << ' ' << t[x].a(oo) << endl;
        return t[x].d - t[x].a(oo); 
    }
    down(x);
    if(p <= mid) return query(x << 1, l, mid, p);
    return query(x << 1 | 1, mid + 1, r, p);
}
#undef mid 

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> n >> q; 
    for(int z = 0; z < q; z++) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        // cout << "FFF " << op << ' ' << l << ' ' << r << endl;
        if(op <= 4) {
            modify(1, 1, n, l, r, op);
        }
        if(op == 5) {
            cout << query(1, 1, n, l) + 500000 << '\n';
        }
        // cerr << "FFFF " << op << ' ' << l << ' ' << r << endl;
        // for(int j = 1; j <= n; j++) {
        //     cerr <<
        //     query(1, 1, n, j) 
        //     << ' '; 
        // }
        // cerr << endl;
    }       
    return 0; 
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 74416kb

input:

1 9
1 1 1
1 1 1
1 1 1
3 1 1
2 1 1
1 1 1
1 1 1
4 1 1
5 1 1

output:

500004

result:

ok 1 number(s): "500004"

Test #2:

score: 0
Accepted
time: 12ms
memory: 75540kb

input:

3 7
2 1 3
3 1 3
1 1 3
1 1 3
5 1 1
4 1 3
5 1 1

output:

500001
499999

result:

ok 2 number(s): "500001 499999"

Test #3:

score: -100
Dangerous Syscalls

input:

500000 500000
2 132991 371170
5 15281 15281
1 278642 397098
2 152103 176573
2 13797 47775
3 139320 370045
3 79054 432340
3 82556 212775
4 270171 469418
5 148000 148000
3 371255 401414
5 71051 71051
2 358945 473071
2 231663 265401
2 20243 58131
1 247710 313373
5 154549 154549
1 17317 233265
5 37602 3...

output:


result: