oj.uz

Submission #940355

# Submission time Handle Problem Language Result Execution time Memory
940355 2024-03-07T08:26:15 Z Sundavar Crossing (JOI21_crossing) C++14
49 / 100
 7000 ms 597116 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> cnt, real_cnt;
        node(){
            cnt.resize(3);
            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].cnt[conv(fake[i])] = 1, 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].cnt[i] = t[v*2].cnt[i]+t[v*2+1].cnt[i];
        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].cnt = {0,0,0};
        t[v].cnt[c] = t[v].all;
        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 = 0;
        for(int i = 0; i < 3; i++)
            t[v].cnt[i] = t[v*2].cnt[i]+t[v*2+1].cnt[i];
        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:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i = 0; i < real.size(); i++){
      |                        ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < trees.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i = 0; i < trees.size(); i++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 67844 KB Output is correct
2 Correct 453 ms 68200 KB Output is correct
3 Correct 501 ms 67900 KB Output is correct
4 Correct 467 ms 68152 KB Output is correct
5 Correct 436 ms 67924 KB Output is correct
6 Correct 413 ms 68056 KB Output is correct
7 Correct 456 ms 68108 KB Output is correct
8 Correct 416 ms 68176 KB Output is correct
9 Correct 430 ms 68324 KB Output is correct
10 Correct 420 ms 68056 KB Output is correct
11 Correct 431 ms 68124 KB Output is correct
12 Correct 416 ms 68268 KB Output is correct
13 Correct 459 ms 68168 KB Output is correct
14 Correct 430 ms 68200 KB Output is correct
15 Correct 418 ms 68180 KB Output is correct
16 Correct 417 ms 67984 KB Output is correct
17 Correct 416 ms 68000 KB Output is correct
18 Correct 430 ms 67924 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 67844 KB Output is correct
2 Correct 453 ms 68200 KB Output is correct
3 Correct 501 ms 67900 KB Output is correct
4 Correct 467 ms 68152 KB Output is correct
5 Correct 436 ms 67924 KB Output is correct
6 Correct 413 ms 68056 KB Output is correct
7 Correct 456 ms 68108 KB Output is correct
8 Correct 416 ms 68176 KB Output is correct
9 Correct 430 ms 68324 KB Output is correct
10 Correct 420 ms 68056 KB Output is correct
11 Correct 431 ms 68124 KB Output is correct
12 Correct 416 ms 68268 KB Output is correct
13 Correct 459 ms 68168 KB Output is correct
14 Correct 430 ms 68200 KB Output is correct
15 Correct 418 ms 68180 KB Output is correct
16 Correct 417 ms 67984 KB Output is correct
17 Correct 416 ms 68000 KB Output is correct
18 Correct 430 ms 67924 KB Output is correct
19 Correct 837 ms 70832 KB Output is correct
20 Correct 668 ms 70968 KB Output is correct
21 Correct 610 ms 70548 KB Output is correct
22 Correct 626 ms 70936 KB Output is correct
23 Correct 449 ms 68944 KB Output is correct
24 Correct 466 ms 68944 KB Output is correct
25 Correct 630 ms 71020 KB Output is correct
26 Correct 657 ms 70844 KB Output is correct
27 Correct 610 ms 70828 KB Output is correct
28 Correct 789 ms 70816 KB Output is correct
29 Correct 642 ms 70728 KB Output is correct
30 Correct 514 ms 68968 KB Output is correct
31 Correct 618 ms 71044 KB Output is correct
32 Correct 668 ms 70696 KB Output is correct
33 Correct 476 ms 68972 KB Output is correct
34 Correct 702 ms 70836 KB Output is correct
35 Correct 641 ms 70380 KB Output is correct
36 Correct 456 ms 68948 KB Output is correct
37 Correct 460 ms 69036 KB Output is correct
38 Correct 646 ms 70788 KB Output is correct
39 Correct 467 ms 70872 KB Output is correct
40 Correct 651 ms 70304 KB Output is correct
41 Correct 948 ms 71108 KB Output is correct
42 Correct 426 ms 70556 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 67844 KB Output is correct
2 Correct 453 ms 68200 KB Output is correct
3 Correct 501 ms 67900 KB Output is correct
4 Correct 467 ms 68152 KB Output is correct
5 Correct 436 ms 67924 KB Output is correct
6 Correct 413 ms 68056 KB Output is correct
7 Correct 456 ms 68108 KB Output is correct
8 Correct 416 ms 68176 KB Output is correct
9 Correct 430 ms 68324 KB Output is correct
10 Correct 420 ms 68056 KB Output is correct
11 Correct 431 ms 68124 KB Output is correct
12 Correct 416 ms 68268 KB Output is correct
13 Correct 459 ms 68168 KB Output is correct
14 Correct 430 ms 68200 KB Output is correct
15 Correct 418 ms 68180 KB Output is correct
16 Correct 417 ms 67984 KB Output is correct
17 Correct 416 ms 68000 KB Output is correct
18 Correct 430 ms 67924 KB Output is correct
19 Correct 1680 ms 593692 KB Output is correct
20 Correct 1904 ms 593392 KB Output is correct
21 Correct 696 ms 199508 KB Output is correct
22 Correct 662 ms 199508 KB Output is correct
23 Correct 681 ms 199500 KB Output is correct
24 Correct 685 ms 199248 KB Output is correct
25 Correct 708 ms 199616 KB Output is correct
26 Correct 667 ms 199524 KB Output is correct
27 Correct 690 ms 199696 KB Output is correct
28 Correct 642 ms 199312 KB Output is correct
29 Correct 699 ms 199764 KB Output is correct
30 Correct 645 ms 199252 KB Output is correct
31 Correct 1674 ms 593488 KB Output is correct
32 Correct 1643 ms 593692 KB Output is correct
33 Correct 1617 ms 594024 KB Output is correct
34 Correct 1600 ms 593232 KB Output is correct
35 Correct 1591 ms 593744 KB Output is correct
36 Correct 1633 ms 593580 KB Output is correct
37 Correct 1574 ms 593744 KB Output is correct
38 Correct 1652 ms 593832 KB Output is correct
39 Correct 1658 ms 593324 KB Output is correct
40 Correct 1643 ms 593676 KB Output is correct
41 Correct 1658 ms 593656 KB Output is correct
42 Correct 1666 ms 593704 KB Output is correct
43 Correct 1628 ms 594020 KB Output is correct
44 Correct 1585 ms 593544 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 67844 KB Output is correct
2 Correct 453 ms 68200 KB Output is correct
3 Correct 501 ms 67900 KB Output is correct
4 Correct 467 ms 68152 KB Output is correct
5 Correct 436 ms 67924 KB Output is correct
6 Correct 413 ms 68056 KB Output is correct
7 Correct 456 ms 68108 KB Output is correct
8 Correct 416 ms 68176 KB Output is correct
9 Correct 430 ms 68324 KB Output is correct
10 Correct 420 ms 68056 KB Output is correct
11 Correct 431 ms 68124 KB Output is correct
12 Correct 416 ms 68268 KB Output is correct
13 Correct 459 ms 68168 KB Output is correct
14 Correct 430 ms 68200 KB Output is correct
15 Correct 418 ms 68180 KB Output is correct
16 Correct 417 ms 67984 KB Output is correct
17 Correct 416 ms 68000 KB Output is correct
18 Correct 430 ms 67924 KB Output is correct
19 Correct 837 ms 70832 KB Output is correct
20 Correct 668 ms 70968 KB Output is correct
21 Correct 610 ms 70548 KB Output is correct
22 Correct 626 ms 70936 KB Output is correct
23 Correct 449 ms 68944 KB Output is correct
24 Correct 466 ms 68944 KB Output is correct
25 Correct 630 ms 71020 KB Output is correct
26 Correct 657 ms 70844 KB Output is correct
27 Correct 610 ms 70828 KB Output is correct
28 Correct 789 ms 70816 KB Output is correct
29 Correct 642 ms 70728 KB Output is correct
30 Correct 514 ms 68968 KB Output is correct
31 Correct 618 ms 71044 KB Output is correct
32 Correct 668 ms 70696 KB Output is correct
33 Correct 476 ms 68972 KB Output is correct
34 Correct 702 ms 70836 KB Output is correct
35 Correct 641 ms 70380 KB Output is correct
36 Correct 456 ms 68948 KB Output is correct
37 Correct 460 ms 69036 KB Output is correct
38 Correct 646 ms 70788 KB Output is correct
39 Correct 467 ms 70872 KB Output is correct
40 Correct 651 ms 70304 KB Output is correct
41 Correct 948 ms 71108 KB Output is correct
42 Correct 426 ms 70556 KB Output is correct
43 Correct 1680 ms 593692 KB Output is correct
44 Correct 1904 ms 593392 KB Output is correct
45 Correct 696 ms 199508 KB Output is correct
46 Correct 662 ms 199508 KB Output is correct
47 Correct 681 ms 199500 KB Output is correct
48 Correct 685 ms 199248 KB Output is correct
49 Correct 708 ms 199616 KB Output is correct
50 Correct 667 ms 199524 KB Output is correct
51 Correct 690 ms 199696 KB Output is correct
52 Correct 642 ms 199312 KB Output is correct
53 Correct 699 ms 199764 KB Output is correct
54 Correct 645 ms 199252 KB Output is correct
55 Correct 1674 ms 593488 KB Output is correct
56 Correct 1643 ms 593692 KB Output is correct
57 Correct 1617 ms 594024 KB Output is correct
58 Correct 1600 ms 593232 KB Output is correct
59 Correct 1591 ms 593744 KB Output is correct
60 Correct 1633 ms 593580 KB Output is correct
61 Correct 1574 ms 593744 KB Output is correct
62 Correct 1652 ms 593832 KB Output is correct
63 Correct 1658 ms 593324 KB Output is correct
64 Correct 1643 ms 593676 KB Output is correct
65 Correct 1658 ms 593656 KB Output is correct
66 Correct 1666 ms 593704 KB Output is correct
67 Correct 1628 ms 594020 KB Output is correct
68 Correct 1585 ms 593544 KB Output is correct
69 Execution timed out 7061 ms 597116 KB Time limit exceeded
70 Halted 0 ms 0 KB -