QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#859877#9986. Shioriucup-team4975#WA 136ms255428kbC++146.5kb2025-01-18 06:24:072025-01-18 06:24:09

Judging History

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

  • [2025-01-18 06:24:09]
  • 评测
  • 测评结果：WA
  • 用时：136ms
  • 内存：255428kb
查看
  • [2025-01-18 06:24:07]
  • 提交

answer

#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'

#define FINISH cerr << "FINISH" << endl;
#define debug(x) cerr << setw(4) << #x << " == " << x << endl

#define debugv(x)                   \
    cerr << setw(4) << #x << ":: "; \
    for (auto i : x)                \
        cerr << i << " ";           \
    cerr << endl

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 500020;

struct Segtree {
    bitset<710> B;
    int l, r;
    ll sum; 
    ll addtag, settag;
}t[N << 2];
int a[N];

void pushup(int p) {
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    t[p].B = t[p << 1].B | t[p << 1 | 1].B;
}

void setp(int p, int val) {
    t[p].B.reset();
    if (t[p].settag < 700) {
        t[p].B.set(t[p].settag, 1);
    }
    t[p].sum = 1ll * (t[p].r - t[p].l + 1) * val;
}

void addp(int p, int val) {
    if (t[p].addtag < 700){
         t[p].B <<= t[p].addtag;
    }
    else
        t[p].B.reset();
    t[p].sum += 1ll * (t[p].r - t[p].l + 1) * val;
}

void pushdown(int p) {
    if (t[p].settag != -1) {
        t[p << 1].addtag = t[p << 1 | 1].addtag = 0;
        t[p << 1].settag = t[p << 1 | 1].settag = t[p].settag;
        setp(p << 1, t[p].settag);
        setp(p << 1 | 1, t[p].settag);
        
        t[p].settag = -1;
    }
    if (t[p].addtag) {
        t[p << 1].addtag += t[p].addtag;
        t[p << 1 | 1].addtag += t[p].addtag;
        addp(p << 1, t[p].addtag);
        addp(p << 1 | 1, t[p].addtag);

        t[p].addtag = 0;
    }
}

void build (int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    t[p].sum = 0;
    t[p].addtag = 0;
    t[p].settag = -1;
    if (l == r) {
        cin >> t[p].sum;
        if (t[p].sum < 700) {
            t[p].B.set(t[p].sum, 1);
        }
        return;
    }
    int mid = (l + r) >> 1;
    build (p << 1, l, mid);
    build (p << 1 | 1, mid + 1, r);
    pushup(p);
}

void modify(int p, int l, int r, int type, int val) {
    if (l <= t[p].l && t[p].r <= r) {
        if (type == 1) {// set
            t[p].addtag = 0;
            t[p].settag = val;
            t[p].B.reset();
            if (t[p].settag < 700) {
                t[p].B.set(t[p].settag, 1);
            }
            t[p].sum = 1ll * (t[p].r - t[p].l + 1) * val;
        }
        if (type == 2) {// add
            t[p].addtag += val;
            if (t[p].addtag < 700){
                t[p].B <<= t[p].addtag;
            }
            else
                t[p].B.reset();
            t[p].sum += 1ll * (t[p].r - t[p].l + 1) * val;
        }
        // cout << "modify::" << endl;
        // cout << t[p].l << " " << t[p].r << endl;
        // bitset<2> B;
        // for (int i = 0; i < 2; i++)B[i] = t[p].B[i];
        // cout << t[p].sum << " " << B << endl;
        return;
    }
    // cout << "before" << endl;
    // cout << p << " " << t[p].l << " " << t[p].r << " " << endl;
    // bitset<2> B;
    // for (int i = 0; i < 2; i++)B[i] = t[p].B[i];
    // cout << t[p].sum << " " << B << endl;
    pushdown(p);
    // cout << "after" << endl;
    // cout << p << " " << t[p].l << " " << t[p].r << " " << endl;
    // B.reset();
    // for (int i = 0; i < 2; i++)B[i] = t[p].B[i];
    // cout << t[p].sum << " " << B << endl;
    if (l <= t[p << 1].r)
        modify(p << 1, l, r, type, val);
    if (r >= t[p << 1 | 1].l)
        modify(p << 1 | 1, l, r, type, val);
    pushup(p);
    // if (t[p].l == 1 && t[p].r == 2) {
    //     B.reset();
    //     for (int i = 0; i < 2; i++)B[i] = t[p << 1].B[i];
    //     cout << B << " ";
    //     B.reset();
    //     for (int i = 0; i < 2; i++)B[i] = t[p << 1 | 1].B[i];
    //     cout << B << endl;
    // }
}

void getall(int p, int l, int r) {
    if (t[p].l == t[p].r) {
        // cout << t[p].sum << " " ;
        if (t[p].sum <= (r - l + 1)) {
            a[t[p].sum] = 1;
        }
        return;
    }
    pushdown(p);
    if (l <= t[p << 1].r)
        getall(p << 1, l, r);
    if (r >= t[p << 1 | 1].l)
        getall(p << 1 | 1, l, r);
    pushup(p);
}

int burteforce(int l, int r) {
    // cout << "!  bf " << l << ' ' << r << endl;
    for (int i = 0; i <= (r - l + 1); i++) 
        a[i] = 0;
    getall(1, l, r);
    // cout << endl;
    // for (int i = 0; i <= r - l + 1; i++) {
    //     cout << a[i] << " ";
    // }
    // cout << endl;
    for (int i = 0; i <= (r - l + 1); i++) {
        if (a[i] == 0)
            return i;
    }
    assert(false);
}

bitset<710> query_mex(int p, int l, int r) {
    if (l <= t[p].l && t[p].r <= r) {
        return t[p].B;
    }
    pushdown(p);
    bitset<710> ans = 0;
    if (l <= t[p << 1].r)
        ans |= query_mex(p << 1, l, r);
    if (r >= t[p << 1 | 1].l)
        ans |= query_mex(p << 1 | 1, l, r);
    pushup(p);
    return ans;
}

ll query_sum (int p, int l, int r) {
    if (l <= t[p].l && t[p].r <= r) {
        return t[p].sum;
    }
    pushdown(p);
    ll ans = 0;
    if (l <= t[p << 1].r)
        ans += query_sum(p << 1, l, r);
    if (r >= t[p << 1 | 1].l)
        ans += query_sum(p << 1 | 1, l, r);
    pushup(p);
    return ans;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    build (1, 1, n);
    for (int i = 1; i <= m; i++) {
        int type, l, r, val;
        cin >> type;
        if (type == 1) {
            cin >> l >> r >> val;
            // cout << "! modify " << l << " " << r << " " << type << " " << val << endl;
            modify(1, l, r, 1, val);
        }
        if (type == 2) {
            cin >> l >> r;
            bitset<710> B = query_mex(1, l, r);
            int ans = -1;
            for (int i = 0; i < 700; i++) {
                if (B[i] == 0) {
                    ans = i;
                    break;
                }
            }
            if (ans == -1) {
                ans = burteforce(l, r);
            }
            // cout << ans << el;
            if (ans != 0)
                modify(1, l, r, 2, ans);
        }
        if (type == 3) {
            
            cin >> l >> r;
            cout << query_sum(1, l, r) << el;
        }
        // cout.flush();

        // burteforce(1, n);
        // cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 27ms
memory: 255428kb

input:

5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5

output:

5
11
22

result:

ok 3 number(s): "5 11 22"

Test #2:

score: 0
Accepted
time: 36ms
memory: 254916kb

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: -100
Wrong Answer
time: 136ms
memory: 254668kb

input:

10 500000
0 0 0 0 0 0 0 0 0 0
3 2 9
2 4 10
2 2 7
2 7 9
3 1 1
3 5 8
1 5 10 0
3 1 9
3 5 9
2 2 4
1 2 4 0
2 5 6
3 8 8
1 4 6 0
1 6 6 0
2 4 10
3 1 9
3 5 7
1 4 10 0
3 6 9
3 2 6
2 1 8
1 5 9 0
3 7 8
3 4 8
2 4 8
2 5 8
2 1 9
2 3 8
1 5 10 0
2 4 8
3 1 6
2 1 4
2 3 7
3 4 10
1 4 6 0
1 1 6 0
2 3 7
1 1 1 0
2 1 10
1 5...

output:

0
0
10
7
0
0
6
3
0
0
0
1
21
11
10
0
0
0
0
17
23
1
20
2
11
27
26
2
18
2
2
0
0
0
2
4
1
0
0
0
7
2
0
4
26
15
7
11
0
4
4
2
7
4
1
6
0
6
0
7
6
3
2
5
0
0
0
7
14
2
5
0
2
0
0
6
12
6
0
2
3
0
0
1
16
12
1
1
12
0
3
4
4
10
3
16
0
17
2
4
0
0
16
8
2
8
18
23
2
24
4
12
7
4
14
5
0
2
8
4
16
10
6
4
21
15
1
3
3
0
2
5
0
2
...

result:

wrong answer 13th numbers differ - expected: '25', found: '21'
English 繁體中文 简体中文

Server Time: 2025-02-02 00:01:08 | OpenSource Project