(cache)Submission #67752980 - Japan Registry Services (JPRS) Programming Contest 2025#2 (AtCoder Beginner Contest 415)

Contest Duration: 2025-07-19(Sat) 21:00 - 2025-07-19(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #67752980

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
using ll = long long;
struct T {
    char left, right;
    int lcnt, rcnt, val;
    bool same_all;
};
T op(const T &a, const T &b) {
    T res;
    res.left = a.left == '\0' ? b.left : a.left;
    res.right = b.right == '\0' ? a.right : b.right;
    if (a.same_all && b.same_all && (a.left == b.left || a.left == '\0' || b.left == '\0')) {
        res.val = a.val + b.val;
        res.lcnt = res.val;
        res.rcnt = res.val;
        res.same_all = true;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
using ll = long long;

struct T {
    char left, right;
    int lcnt, rcnt, val;
    bool same_all;
};

T op(const T &a, const T &b) {
    T res;
    res.left = a.left == '\0' ? b.left : a.left;
    res.right = b.right == '\0' ? a.right : b.right;
    if (a.same_all && b.same_all && (a.left == b.left || a.left == '\0' || b.left == '\0')) {
        res.val = a.val + b.val;
        res.lcnt = res.val;
        res.rcnt = res.val;
        res.same_all = true;
    } else {
        res.val = max(a.val, b.val);
        if (a.right == b.left) {
            res.val = max(res.val, a.rcnt + b.lcnt);
        }
        res.rcnt = (b.right == '\0' ? a.rcnt : b.rcnt);
        if (b.same_all && (a.right == b.left)) {
            res.rcnt += a.rcnt;
        }
        res.lcnt = (a.left == '\0' ? b.lcnt : a.lcnt);
        if (a.same_all && (a.right == b.left)) {
            res.lcnt += b.lcnt;
        }
        res.same_all = false;
    }
    return res;
}

T e() {
    T res;
    res.left = res.right = '\0';
    res.lcnt = res.rcnt = 0;
    res.val = 0;
    res.same_all = true; // Empty segment is considered same
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    segtree<T, op, e> seg(N);
    for (int i = 0; i < N; ++i) {
        seg.set(i, {S[i], S[i], 1, 1, 1, true});
    }
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int i;
            char c;
            cin >> i >> c;
            --i; // Convert to 0-based index
            seg.set(i, {c, c, 1, 1, 1, true});
        } else {
            int l, r;
            cin >> l >> r;
            --l; // Convert to 0-based index
            --r; // Convert to 0-based index
            T res = seg.prod(l, r + 1);
            cout << res.val << '\n';
        }
    }
    return 0;
}

Submission Info

Submission Time	2025-07-19 22:29:05
Task	F - Max Combo
User	katsumata68
Language	C++ 23 (gcc 12.2)
Score	525
Code Size	2051 Byte
Status	AC
Exec Time	377 ms
Memory	34088 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

525 / 525

Status

× 2

× 74

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt
All	evil_01.txt, evil_02.txt, evil_03.txt, evil_04.txt, evil_05.txt, evil_06.txt, evil_07.txt, evil_08.txt, evil_09.txt, evil_10.txt, evil_11.txt, evil_12.txt, evil_13.txt, evil_14.txt, evil_15.txt, evil_16.txt, evil_17.txt, evil_18.txt, evil_19.txt, evil_20.txt, evil_21.txt, evil_22.txt, evil_23.txt, evil_24.txt, evil_25.txt, evil_26.txt, evil_27.txt, evil_28.txt, sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt

Case Name	Status	Exec Time	Memory
evil_01.txt	AC	292 ms	33988 KiB
evil_02.txt	AC	314 ms	33912 KiB
evil_03.txt	AC	297 ms	34016 KiB
evil_04.txt	AC	320 ms	34084 KiB
evil_05.txt	AC	327 ms	33916 KiB
evil_06.txt	AC	357 ms	33952 KiB
evil_07.txt	AC	299 ms	33992 KiB
evil_08.txt	AC	321 ms	33836 KiB
evil_09.txt	AC	322 ms	34008 KiB
evil_10.txt	AC	352 ms	33988 KiB
evil_11.txt	AC	329 ms	34016 KiB
evil_12.txt	AC	356 ms	34012 KiB
evil_13.txt	AC	321 ms	34028 KiB
evil_14.txt	AC	347 ms	34008 KiB
evil_15.txt	AC	300 ms	33956 KiB
evil_16.txt	AC	320 ms	34036 KiB
evil_17.txt	AC	317 ms	34028 KiB
evil_18.txt	AC	342 ms	33992 KiB
evil_19.txt	AC	325 ms	34080 KiB
evil_20.txt	AC	350 ms	33960 KiB
evil_21.txt	AC	319 ms	33976 KiB
evil_22.txt	AC	330 ms	33880 KiB
evil_23.txt	AC	319 ms	33936 KiB
evil_24.txt	AC	330 ms	33984 KiB
evil_25.txt	AC	307 ms	33992 KiB
evil_26.txt	AC	306 ms	33872 KiB
evil_27.txt	AC	255 ms	33940 KiB
evil_28.txt	AC	304 ms	33912 KiB
sample_01.txt	AC	1 ms	3508 KiB
sample_02.txt	AC	1 ms	3488 KiB
test_01.txt	AC	333 ms	33964 KiB
test_02.txt	AC	337 ms	33916 KiB
test_03.txt	AC	333 ms	34012 KiB
test_04.txt	AC	336 ms	33960 KiB
test_05.txt	AC	334 ms	33984 KiB
test_06.txt	AC	336 ms	33964 KiB
test_07.txt	AC	338 ms	33972 KiB
test_08.txt	AC	342 ms	33956 KiB
test_09.txt	AC	374 ms	33984 KiB
test_10.txt	AC	377 ms	33932 KiB
test_11.txt	AC	370 ms	33944 KiB
test_12.txt	AC	373 ms	33976 KiB
test_13.txt	AC	373 ms	33876 KiB
test_14.txt	AC	376 ms	33968 KiB
test_15.txt	AC	377 ms	33936 KiB
test_16.txt	AC	375 ms	33960 KiB
test_17.txt	AC	372 ms	33840 KiB
test_18.txt	AC	377 ms	33840 KiB
test_19.txt	AC	119 ms	3552 KiB
test_20.txt	AC	119 ms	3648 KiB
test_21.txt	AC	127 ms	3492 KiB
test_22.txt	AC	125 ms	3560 KiB
test_23.txt	AC	121 ms	3564 KiB
test_24.txt	AC	120 ms	3556 KiB
test_25.txt	AC	116 ms	3572 KiB
test_26.txt	AC	116 ms	3436 KiB
test_27.txt	AC	116 ms	3572 KiB
test_28.txt	AC	116 ms	3492 KiB
test_29.txt	AC	221 ms	33916 KiB
test_30.txt	AC	220 ms	33956 KiB
test_31.txt	AC	334 ms	33972 KiB
test_32.txt	AC	334 ms	33960 KiB
test_33.txt	AC	338 ms	33984 KiB
test_34.txt	AC	337 ms	33840 KiB
test_35.txt	AC	334 ms	33920 KiB
test_36.txt	AC	335 ms	34012 KiB
test_37.txt	AC	338 ms	33936 KiB
test_38.txt	AC	337 ms	34084 KiB
test_39.txt	AC	352 ms	33916 KiB
test_40.txt	AC	344 ms	33916 KiB
test_41.txt	AC	367 ms	34088 KiB
test_42.txt	AC	361 ms	33916 KiB
test_43.txt	AC	309 ms	33952 KiB
test_44.txt	AC	310 ms	33952 KiB