oj.uz

Submission #940362

# Submission time Handle Problem Language Result Execution time Memory
940362 2024-03-07T08:31:11 Z Sundavar Crossing (JOI21_crossing) C++14
100 / 100
 4498 ms 339616 KB 
#include <bits/stdc++.h>
using namespace std;
int conv(char c){
    if(c == 'I') return 0;
    if(c == 'J') return 1;
    return 2;
}

struct segTree{
    struct node{
        vector<int> real_cnt;
        node(){
            real_cnt.resize(3);
        }
        int wrong = 0, set_to = -1, all = 0;
    };
    vector<node> t;
    int maxN = (1<<18);
    segTree(string& real, string& fake){
        t.resize(2*maxN);
        for(int i = 0; i < real.size(); i++){
            t[i+maxN].real_cnt[conv(real[i])] = 1;
            t[i+maxN].wrong = fake[i] != real[i];
            t[i+maxN].all = 1;
        }
        build(1, 0, maxN);
    }
    void build(int v, int l, int r){
        if(r-l == 1) return;
        build(2*v, l, (l+r)/2), build(2*v+1, (l+r)/2, r);
        t[v].all = t[v*2].all + t[v*2+1].all;
        t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
        for(int i = 0; i < 3; i++)
            t[v].real_cnt[i] = t[v*2].real_cnt[i]+t[v*2+1].real_cnt[i];

    }
    void add(int v, int c){
        t[v].wrong = t[v].all - t[v].real_cnt[c];
        t[v].set_to = c; 
    }
    void push(int v){
        if(t[v].set_to == -1) return;
        add(2*v, t[v].set_to), add(2*v+1, t[v].set_to);
        t[v].set_to = -1;
    }
    void upd(int l, int r, int c){
        upd(1, l, r, 0, maxN, c);
    }
    void upd(int v, int ll, int rr, int l, int r, int c){
        if(min(r,rr) <= max(l,ll)) return;
        if(ll <= l && r <= rr){
            add(v, c);
            return;
        }
        push(v);
        upd(2*v, ll, rr, l, (l+r)/2, c), upd(2*v+1, ll, rr, (l+r)/2, r, c);
        t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
    }
};

char cross(char c1, char c2){
    if(c2 < c1) swap(c1, c2);
    if(c1 == c2) return c1;
    if(c1 == 'I' && c2 == 'O') return 'J';
    if(c1 == 'I' && c2 == 'J') return 'O';
    return 'I';
}

int main(){
    int n;
    cin>>n;
    set<string> v;
    for(int i = 0; i < 3; i++){
        string s;
        cin>>s;
        v.insert(s);
    }
    while(true){
        bool added = false;
        for(auto it = v.begin(); it != v.end(); it++)
            for(auto it2 = v.begin(); it2 != it; it2++){
                string s1 = *it, s2 = *it2;
                string s = "";
                for(int k = 0; k < n; k++)
                    s += cross(s1[k], s2[k]);
                if(v.count(s) == 0){
                    added = true;
                    v.insert(s);
                }
            }
        if(!added) break;
    }
    int q;
    string fake;
    cin>>q>>fake;
    vector<segTree> trees;
    for(auto it = v.begin(); it != v.end(); it++){
        string s = *it;
        trees.push_back(segTree(s, fake));
    }
    bool any = false;
    for(int i = 0; i < trees.size(); i++)
        any |= trees[i].t[1].wrong == 0;
    cout << (any ? "Yes" : "No") << "\n";

    while(q--){
        int a, b;
        char c;
        cin>>a>>b>>c;
        bool any = false;
        for(int i = 0; i < trees.size(); i++){
            trees[i].upd(a-1, b, conv(c));
            any |= trees[i].t[1].wrong == 0; 
        }
        cout << (any ? "Yes" : "No") << "\n";
    }
}

Compilation message

Main.cpp: In constructor 'segTree::segTree(std::string&, std::string&)':
Main.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i < real.size(); i++){
      |                        ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < trees.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int i = 0; i < trees.size(); i++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 39160 KB Output is correct
2 Correct 380 ms 38920 KB Output is correct
3 Correct 371 ms 38852 KB Output is correct
4 Correct 405 ms 38792 KB Output is correct
5 Correct 366 ms 38824 KB Output is correct
6 Correct 362 ms 38992 KB Output is correct
7 Correct 382 ms 38872 KB Output is correct
8 Correct 371 ms 39012 KB Output is correct
9 Correct 371 ms 38872 KB Output is correct
10 Correct 385 ms 38844 KB Output is correct
11 Correct 377 ms 39440 KB Output is correct
12 Correct 386 ms 38820 KB Output is correct
13 Correct 390 ms 38872 KB Output is correct
14 Correct 366 ms 38992 KB Output is correct
15 Correct 383 ms 38752 KB Output is correct
16 Correct 375 ms 38924 KB Output is correct
17 Correct 394 ms 38776 KB Output is correct
18 Correct 370 ms 38972 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 39160 KB Output is correct
2 Correct 380 ms 38920 KB Output is correct
3 Correct 371 ms 38852 KB Output is correct
4 Correct 405 ms 38792 KB Output is correct
5 Correct 366 ms 38824 KB Output is correct
6 Correct 362 ms 38992 KB Output is correct
7 Correct 382 ms 38872 KB Output is correct
8 Correct 371 ms 39012 KB Output is correct
9 Correct 371 ms 38872 KB Output is correct
10 Correct 385 ms 38844 KB Output is correct
11 Correct 377 ms 39440 KB Output is correct
12 Correct 386 ms 38820 KB Output is correct
13 Correct 390 ms 38872 KB Output is correct
14 Correct 366 ms 38992 KB Output is correct
15 Correct 383 ms 38752 KB Output is correct
16 Correct 375 ms 38924 KB Output is correct
17 Correct 394 ms 38776 KB Output is correct
18 Correct 370 ms 38972 KB Output is correct
19 Correct 569 ms 40556 KB Output is correct
20 Correct 513 ms 40740 KB Output is correct
21 Correct 474 ms 40324 KB Output is correct
22 Correct 484 ms 40236 KB Output is correct
23 Correct 414 ms 39580 KB Output is correct
24 Correct 418 ms 39296 KB Output is correct
25 Correct 572 ms 40428 KB Output is correct
26 Correct 519 ms 40748 KB Output is correct
27 Correct 510 ms 40372 KB Output is correct
28 Correct 541 ms 40488 KB Output is correct
29 Correct 528 ms 40648 KB Output is correct
30 Correct 404 ms 39604 KB Output is correct
31 Correct 523 ms 40456 KB Output is correct
32 Correct 513 ms 40496 KB Output is correct
33 Correct 404 ms 39520 KB Output is correct
34 Correct 615 ms 40600 KB Output is correct
35 Correct 446 ms 40268 KB Output is correct
36 Correct 439 ms 39432 KB Output is correct
37 Correct 411 ms 39480 KB Output is correct
38 Correct 465 ms 40888 KB Output is correct
39 Correct 417 ms 40376 KB Output is correct
40 Correct 501 ms 40044 KB Output is correct
41 Correct 617 ms 40660 KB Output is correct
42 Correct 376 ms 40452 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 39160 KB Output is correct
2 Correct 380 ms 38920 KB Output is correct
3 Correct 371 ms 38852 KB Output is correct
4 Correct 405 ms 38792 KB Output is correct
5 Correct 366 ms 38824 KB Output is correct
6 Correct 362 ms 38992 KB Output is correct
7 Correct 382 ms 38872 KB Output is correct
8 Correct 371 ms 39012 KB Output is correct
9 Correct 371 ms 38872 KB Output is correct
10 Correct 385 ms 38844 KB Output is correct
11 Correct 377 ms 39440 KB Output is correct
12 Correct 386 ms 38820 KB Output is correct
13 Correct 390 ms 38872 KB Output is correct
14 Correct 366 ms 38992 KB Output is correct
15 Correct 383 ms 38752 KB Output is correct
16 Correct 375 ms 38924 KB Output is correct
17 Correct 394 ms 38776 KB Output is correct
18 Correct 370 ms 38972 KB Output is correct
19 Correct 1034 ms 333480 KB Output is correct
20 Correct 1037 ms 333368 KB Output is correct
21 Correct 517 ms 111688 KB Output is correct
22 Correct 514 ms 111760 KB Output is correct
23 Correct 565 ms 111844 KB Output is correct
24 Correct 500 ms 111700 KB Output is correct
25 Correct 546 ms 111744 KB Output is correct
26 Correct 523 ms 111764 KB Output is correct
27 Correct 528 ms 111772 KB Output is correct
28 Correct 505 ms 111868 KB Output is correct
29 Correct 517 ms 112212 KB Output is correct
30 Correct 489 ms 111852 KB Output is correct
31 Correct 949 ms 333404 KB Output is correct
32 Correct 1000 ms 333364 KB Output is correct
33 Correct 942 ms 333932 KB Output is correct
34 Correct 949 ms 333564 KB Output is correct
35 Correct 963 ms 333656 KB Output is correct
36 Correct 995 ms 333396 KB Output is correct
37 Correct 976 ms 333840 KB Output is correct
38 Correct 999 ms 333476 KB Output is correct
39 Correct 971 ms 333328 KB Output is correct
40 Correct 982 ms 333680 KB Output is correct
41 Correct 1062 ms 333596 KB Output is correct
42 Correct 1069 ms 333420 KB Output is correct
43 Correct 1030 ms 333452 KB Output is correct
44 Correct 1079 ms 333724 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 39160 KB Output is correct
2 Correct 380 ms 38920 KB Output is correct
3 Correct 371 ms 38852 KB Output is correct
4 Correct 405 ms 38792 KB Output is correct
5 Correct 366 ms 38824 KB Output is correct
6 Correct 362 ms 38992 KB Output is correct
7 Correct 382 ms 38872 KB Output is correct
8 Correct 371 ms 39012 KB Output is correct
9 Correct 371 ms 38872 KB Output is correct
10 Correct 385 ms 38844 KB Output is correct
11 Correct 377 ms 39440 KB Output is correct
12 Correct 386 ms 38820 KB Output is correct
13 Correct 390 ms 38872 KB Output is correct
14 Correct 366 ms 38992 KB Output is correct
15 Correct 383 ms 38752 KB Output is correct
16 Correct 375 ms 38924 KB Output is correct
17 Correct 394 ms 38776 KB Output is correct
18 Correct 370 ms 38972 KB Output is correct
19 Correct 569 ms 40556 KB Output is correct
20 Correct 513 ms 40740 KB Output is correct
21 Correct 474 ms 40324 KB Output is correct
22 Correct 484 ms 40236 KB Output is correct
23 Correct 414 ms 39580 KB Output is correct
24 Correct 418 ms 39296 KB Output is correct
25 Correct 572 ms 40428 KB Output is correct
26 Correct 519 ms 40748 KB Output is correct
27 Correct 510 ms 40372 KB Output is correct
28 Correct 541 ms 40488 KB Output is correct
29 Correct 528 ms 40648 KB Output is correct
30 Correct 404 ms 39604 KB Output is correct
31 Correct 523 ms 40456 KB Output is correct
32 Correct 513 ms 40496 KB Output is correct
33 Correct 404 ms 39520 KB Output is correct
34 Correct 615 ms 40600 KB Output is correct
35 Correct 446 ms 40268 KB Output is correct
36 Correct 439 ms 39432 KB Output is correct
37 Correct 411 ms 39480 KB Output is correct
38 Correct 465 ms 40888 KB Output is correct
39 Correct 417 ms 40376 KB Output is correct
40 Correct 501 ms 40044 KB Output is correct
41 Correct 617 ms 40660 KB Output is correct
42 Correct 376 ms 40452 KB Output is correct
43 Correct 1034 ms 333480 KB Output is correct
44 Correct 1037 ms 333368 KB Output is correct
45 Correct 517 ms 111688 KB Output is correct
46 Correct 514 ms 111760 KB Output is correct
47 Correct 565 ms 111844 KB Output is correct
48 Correct 500 ms 111700 KB Output is correct
49 Correct 546 ms 111744 KB Output is correct
50 Correct 523 ms 111764 KB Output is correct
51 Correct 528 ms 111772 KB Output is correct
52 Correct 505 ms 111868 KB Output is correct
53 Correct 517 ms 112212 KB Output is correct
54 Correct 489 ms 111852 KB Output is correct
55 Correct 949 ms 333404 KB Output is correct
56 Correct 1000 ms 333364 KB Output is correct
57 Correct 942 ms 333932 KB Output is correct
58 Correct 949 ms 333564 KB Output is correct
59 Correct 963 ms 333656 KB Output is correct
60 Correct 995 ms 333396 KB Output is correct
61 Correct 976 ms 333840 KB Output is correct
62 Correct 999 ms 333476 KB Output is correct
63 Correct 971 ms 333328 KB Output is correct
64 Correct 982 ms 333680 KB Output is correct
65 Correct 1062 ms 333596 KB Output is correct
66 Correct 1069 ms 333420 KB Output is correct
67 Correct 1030 ms 333452 KB Output is correct
68 Correct 1079 ms 333724 KB Output is correct
69 Correct 4017 ms 335168 KB Output is correct
70 Correct 3744 ms 339168 KB Output is correct
71 Correct 723 ms 114236 KB Output is correct
72 Correct 682 ms 114232 KB Output is correct
73 Correct 637 ms 114260 KB Output is correct
74 Correct 944 ms 115684 KB Output is correct
75 Correct 630 ms 114228 KB Output is correct
76 Correct 994 ms 116328 KB Output is correct
77 Correct 914 ms 115820 KB Output is correct
78 Correct 588 ms 114388 KB Output is correct
79 Correct 595 ms 114396 KB Output is correct
80 Correct 2253 ms 338264 KB Output is correct
81 Correct 1264 ms 335800 KB Output is correct
82 Correct 2518 ms 339616 KB Output is correct
83 Correct 2527 ms 338992 KB Output is correct
84 Correct 1315 ms 336188 KB Output is correct
85 Correct 1351 ms 335772 KB Output is correct
86 Correct 2843 ms 338240 KB Output is correct
87 Correct 3157 ms 339396 KB Output is correct
88 Correct 1376 ms 336104 KB Output is correct
89 Correct 2728 ms 338756 KB Output is correct
90 Correct 2937 ms 339236 KB Output is correct
91 Correct 1329 ms 336496 KB Output is correct
92 Correct 2222 ms 338180 KB Output is correct
93 Correct 1326 ms 336028 KB Output is correct
94 Correct 1351 ms 335912 KB Output is correct
95 Correct 1273 ms 335956 KB Output is correct
96 Correct 474 ms 41908 KB Output is correct
97 Correct 1042 ms 339336 KB Output is correct
98 Correct 2327 ms 338332 KB Output is correct
99 Correct 4498 ms 339412 KB Output is correct
100 Correct 1095 ms 338764 KB Output is correct