QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165794#6733. Moniphant Sleepucup-team1209TL 12ms81612kbC++143.9kb2023-09-05 21:46:322023-09-05 22:11:34

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 22:11:34]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:12ms
  • 内存:81612kb
  • [2023-09-05 21:58:11]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-09-05 21:57:56]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:8ms
  • 内存:81700kb
  • [2023-09-05 21:46:32]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-09-05 21:46:32]
  • 提交

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 () (cs int &x) {
        if(x == oo) return vi;
        if(x <= p) return v1; 
        return fix(v2 + x - p); 
    }
    void fit () {
        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));
    assert(0);
}



func F(func a, func b) {
    func c; 
    if(a.p == oo) {
        c = func (a.v1, oo, 0, a(b.vi));
        // for(int i = 0; i <= 10; i++) 
        //     assert(c(i) == a(b(i)));
        // assert(c(oo) == a(b(oo)));
        c.fit();
        return c; 
    }
    if(b.p == oo) {
        c = func (a(b.v1), oo, 0, a(b.vi)); 
        // for(int i = 0; i <= 10; i++) 
        //     assert(c(i) == a(b(i)));
        // assert(c(oo) == a(b(oo)));
        c.fit();
        return c;
    }
    c.vi = a(b.vi);
    c.p = b.p; 
    c.v1 = a(b.v1);
    if(a.p > b.v2) {
        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)));

    c.fit();

    return c; 
}

func flat (func x) {
    if(x.v1 == oo) x.v1 = 0; 
    if(x.vi == oo) x.vi = 0; 
    return x; 
}

struct skip {
    func a, c; 
    int d; 
    bool add;
    skip (func a = func(0, oo, 0, 0), func c = func(0, -1, -1, oo), int d = 0, bool add = 0) 
        : a(a), c(c), d(d), add(add) {}
    void operator += (cs skip &x) {
        if(x.add) {
            a = a + flat (F(x.a, c));
            add = 1; 
        }
        d += x.d; 
        c = F(x.c, c);
    }
};
#define mid ((l + r) >> 1) 
skip t[N << 2];

skip a[4] = {
    skip(func(0, oo, 0, 0), func(0, -1, 0, oo), 1, 0),
    skip(func(0, oo, 0, 0), func(oo, 0, -1, oo), -1, 0),
    skip(func(0, oo, 0, 0), func(0, -1, -1, 0), 0, 0),
    skip(func(0, -1, -1, 0), func(oo, oo, 0, oo), 0, 1)
};


void pbpb(skip & c, int op) {
    c += a[op - 1]; 
}

void put(int x, skip c) {
    t[x] += c; 
}

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

void modify (int x, int l, int r, int L, int R, int op) {
    if(L <= l && r <= R) {
        pbpb(t[x], op);
        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) {
        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);
        if(op <= 4) {
            modify(1, 1, n, l, r, op);
        }
        if(op == 5) {
            cout << query(1, 1, n, l) + 500000 << '\n';
        }
    }       
    return 0; 
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 81612kb

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: 81496kb

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
Time Limit Exceeded

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:

500000
499999
500000
499998
499999
500000
500000
499997
500000
499997
499997
499999
499998
500000
499997
500000
499999
500001
499999
499999
499997
499997
499996
499998
500000
500001
500001
499996
499998
499999
499996
499999
500001
500000
500000
500002
500002
499997
500001
499997
499995
499999
500004...

result: