oj.uz

답안 #936732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936732 2024-03-02T16:04:45 Z ace5 Crossing (JOI21_crossing) C++17
49 / 100
 3092 ms 93544 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

int getint(char c)
{
    return (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
}

struct SegTree3
{
    SegTree3(vector<int> _a){a = _a;};
    SegTree3(){a = {};};

    vector<int> a;

    void modify(int i,int x,int l,int r,int indV)
    {
        if(l > i || r < i)
            return ;
        else if(l == r)
        {
            a[indV] = x;
            return ;
        }
        int m = (l+r)/2;
        modify(i,x,l,m,indV*2+1);
        modify(i,x,m+1,r,indV*2+2);
        a[indV] = (a[indV*2+1] == a[indV*2+2] ? a[indV*2+1] : -1);
        return ;
    }
    int get(int lx,int rx,int l,int r,int indV)
    {
        if(l > rx || r < lx)
            return 4;
        else if(l >= lx && r <= rx)
            return a[indV];
        int m = (l+r)/2;
        int sl = get(lx,rx,l,m,indV*2+1);
        int sr = get(lx,rx,m+1,r,indV*2+2);
        return (sl == 4 ? sr : (sr == 4 ? sl : (sl == sr ? sl : -1)));
    }
};

struct Streq
{
    Streq(SegTree3 _et,set<pair<pair<int,int>,pair<int,int>>> _seg){et = _et;seg = _seg;};
    Streq(){et = SegTree3();seg = {};};
    SegTree3 et;
    set<pair<pair<int,int>,pair<int,int>>> seg;
    int kps =  0;
    int ts = 0;

    bool isGood()
    {
        return kps == 0;
    }
    void modify(int l,int r,int f)
    {
        if(l > r)
            return ;
        while(true)
        {
           // cout << 1 << endl;
           // cout << seg.size() << "\n";
            auto it = seg.lower_bound(make_pair(make_pair(l,1e6),make_pair(1e6,1e6)));
            if(it != seg.begin())
            {
                it--;
            }
            if(it == seg.end())
                break;
            pair<pair<int,int>,pair<int,int>> cur = *it;
            if(max(cur.first.first,l) > min(cur.first.second,r))
            {
               // cout << "!" << endl;
                it++;
               // cout << "!" << endl;
                if(it != seg.end())
                    cur = *it;
            }
           // cout << "!" << endl;
            if(max(cur.first.first,l) > min(cur.first.second,r))
                break;
           // cout << 2 << endl;
            kps -= (cur.second.second == 1);
            seg.erase(it);
            if(cur.first.first < l && cur.first.second > r)
            {
                pair<int,int> o1 = {cur.first.first,l-1};
                pair<int,int> o2 = {r+1,cur.first.second};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                bool g2 = (et.get(o2.first,o2.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);
                }
                if(o2.first <= o2.second)
                {
                    seg.insert({o2,{cur.second.first,!g2}});
                    kps += (!g2);
                }
            }
            else if(cur.first.second > r)
            {
                pair<int,int> o1 = {r+1,cur.first.second};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);

                }
            }
            else if(cur.first.first < l)
            {
                pair<int,int> o1 = {cur.first.first,l-1};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);
                }
            }
           // cout << 3 << endl;
        }
       // cout << "!" << endl;
        bool gg = (et.get(l,r,0,ts-1,0) == f);
        seg.insert({{l,r},{f,!gg}});
        kps += (!gg);
      //  cout << kps << "\n";
       // cout << "!" << endl;
    }
};

vector<vector<Streq>> ms(5,vector<Streq>(3));

bool can_get()
{
    bool no = 0;
    for(int i = 0;i < 5;++i)
    {
        bool y = 0;
        for(int j = 0;j < 3;++j)
        {
            if(ms[i][j].isGood())
                y = 1;
        }
        if(!y)
            no = 1;
    }
    return !no;
}
void print_ans()
{
    cout << (can_get() ? "Yes\n" : "No\n");
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string aa,bb,cc;
    cin >> aa >> bb >> cc;
    vector<int> a(n),b(n),c(n);
    for(int i = 0;i < n;++i)
    {
        a[i] = getint(aa[i]);
        b[i] = getint(bb[i]);
        c[i] = getint(cc[i]);
    }
    vector<vector<int>> ix(5);
    vector<vector<int>> ind;
    for(int i = 0;i < n;++i)
    {
        if(a[i] == b[i] && a[i] != c[i])
        {
            ix[0].push_back(i);
            ind.push_back({a[i],c[i],3 - a[i] - c[i]});
        }
        if(a[i] == c[i] && a[i] != b[i])
        {
            ix[1].push_back(i);
            ind.push_back({a[i],b[i],3 - a[i] - b[i]});
        }
        if(c[i] == b[i] && a[i] != c[i])
        {
            ix[2].push_back(i);
            ind.push_back({b[i],a[i],3 - a[i] - b[i]});
        }
        if(a[i] != b[i] && a[i] != c[i] && b[i] != c[i])
        {
            ix[3].push_back(i);
            ind.push_back({a[i],b[i],c[i]});
        }
        if(a[i] == b[i] && b[i] ==c[i])
        {
            ix[4].push_back(i);
            ind.push_back({a[i],a[i],a[i]});
        }
    }
    int q;
    cin >> q;
    string t0;
    cin >> t0;
    for(int i = 0;i < 5;++i)
    {
        for(int j = 0;j < 3;++j)
        {
            vector<int> tet,tcur;
            for(int k = 0;k < ix[i].size();++k)
            {
                tet.push_back(ind[ix[i][k]][j]);
                tcur.push_back(getint(t0[ix[i][k]]));
            }
            ms[i][j].et.a.resize(4*tet.size());
            ms[i][j].ts = tet.size();
            for(int k = 0;k < tet.size();++k)
            {
                ms[i][j].et.modify(k,tet[k],0,int(tet.size())-1,0);
            }

            for(int k = 0;k < tet.size();++k)
            {
                ms[i][j].seg.insert({{k,k},{tcur[k],tcur[k] != tet[k]}});
                ms[i][j].kps += (tcur[k] != tet[k]);
            }
        }
    }
    print_ans();
    while(q--)
    {
        int l,r;
        char cc;
        cin >> l >> r >> cc;
        l--;
        r--;
        int f = getint(cc);
        for(int i = 0;i < 5;++i)
        {
            int lg = lower_bound(ix[i].begin(),ix[i].end(),l)-ix[i].begin();
            int rg = upper_bound(ix[i].begin(),ix[i].end(),r)-ix[i].begin()-1;
            for(int j = 0;j < 3;++j)
                ms[i][j].modify(lg,rg,f);
        }
        print_ans();
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:217:29: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |             for(int k = 0;k < ix[i].size();++k)
      |                           ~~^~~~~~~~~~~~~~
Main.cpp:224:29: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for(int k = 0;k < tet.size();++k)
      |                           ~~^~~~~~~~~~~~
Main.cpp:229:29: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |             for(int k = 0;k < tet.size();++k)
      |                           ~~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 2388 KB Output is correct
2 Correct 353 ms 2416 KB Output is correct
3 Correct 274 ms 2504 KB Output is correct
4 Correct 318 ms 2440 KB Output is correct
5 Correct 278 ms 2344 KB Output is correct
6 Correct 287 ms 2600 KB Output is correct
7 Correct 281 ms 2532 KB Output is correct
8 Correct 303 ms 2388 KB Output is correct
9 Correct 299 ms 2544 KB Output is correct
10 Correct 296 ms 2896 KB Output is correct
11 Correct 311 ms 2596 KB Output is correct
12 Correct 294 ms 2388 KB Output is correct
13 Correct 300 ms 2464 KB Output is correct
14 Correct 291 ms 2384 KB Output is correct
15 Correct 304 ms 2740 KB Output is correct
16 Correct 294 ms 2576 KB Output is correct
17 Correct 306 ms 2664 KB Output is correct
18 Correct 222 ms 2308 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 2388 KB Output is correct
2 Correct 353 ms 2416 KB Output is correct
3 Correct 274 ms 2504 KB Output is correct
4 Correct 318 ms 2440 KB Output is correct
5 Correct 278 ms 2344 KB Output is correct
6 Correct 287 ms 2600 KB Output is correct
7 Correct 281 ms 2532 KB Output is correct
8 Correct 303 ms 2388 KB Output is correct
9 Correct 299 ms 2544 KB Output is correct
10 Correct 296 ms 2896 KB Output is correct
11 Correct 311 ms 2596 KB Output is correct
12 Correct 294 ms 2388 KB Output is correct
13 Correct 300 ms 2464 KB Output is correct
14 Correct 291 ms 2384 KB Output is correct
15 Correct 304 ms 2740 KB Output is correct
16 Correct 294 ms 2576 KB Output is correct
17 Correct 306 ms 2664 KB Output is correct
18 Correct 222 ms 2308 KB Output is correct
19 Correct 1047 ms 93544 KB Output is correct
20 Correct 908 ms 92932 KB Output is correct
21 Correct 1283 ms 88176 KB Output is correct
22 Correct 1069 ms 80180 KB Output is correct
23 Correct 566 ms 7928 KB Output is correct
24 Correct 566 ms 7988 KB Output is correct
25 Correct 1341 ms 92504 KB Output is correct
26 Correct 1200 ms 92100 KB Output is correct
27 Correct 902 ms 92568 KB Output is correct
28 Correct 982 ms 92084 KB Output is correct
29 Correct 889 ms 91836 KB Output is correct
30 Correct 519 ms 8056 KB Output is correct
31 Correct 904 ms 93404 KB Output is correct
32 Correct 922 ms 86052 KB Output is correct
33 Correct 542 ms 7820 KB Output is correct
34 Correct 1014 ms 93408 KB Output is correct
35 Correct 1153 ms 71144 KB Output is correct
36 Correct 542 ms 7904 KB Output is correct
37 Correct 540 ms 7828 KB Output is correct
38 Correct 741 ms 91716 KB Output is correct
39 Correct 658 ms 93076 KB Output is correct
40 Correct 1238 ms 61388 KB Output is correct
41 Correct 1038 ms 92560 KB Output is correct
42 Correct 298 ms 91536 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 2388 KB Output is correct
2 Correct 353 ms 2416 KB Output is correct
3 Correct 274 ms 2504 KB Output is correct
4 Correct 318 ms 2440 KB Output is correct
5 Correct 278 ms 2344 KB Output is correct
6 Correct 287 ms 2600 KB Output is correct
7 Correct 281 ms 2532 KB Output is correct
8 Correct 303 ms 2388 KB Output is correct
9 Correct 299 ms 2544 KB Output is correct
10 Correct 296 ms 2896 KB Output is correct
11 Correct 311 ms 2596 KB Output is correct
12 Correct 294 ms 2388 KB Output is correct
13 Correct 300 ms 2464 KB Output is correct
14 Correct 291 ms 2384 KB Output is correct
15 Correct 304 ms 2740 KB Output is correct
16 Correct 294 ms 2576 KB Output is correct
17 Correct 306 ms 2664 KB Output is correct
18 Correct 222 ms 2308 KB Output is correct
19 Correct 695 ms 2460 KB Output is correct
20 Correct 507 ms 2348 KB Output is correct
21 Correct 345 ms 2416 KB Output is correct
22 Correct 308 ms 2300 KB Output is correct
23 Correct 357 ms 2476 KB Output is correct
24 Correct 373 ms 2656 KB Output is correct
25 Correct 350 ms 2380 KB Output is correct
26 Correct 325 ms 2384 KB Output is correct
27 Correct 349 ms 2592 KB Output is correct
28 Correct 314 ms 2388 KB Output is correct
29 Correct 361 ms 2744 KB Output is correct
30 Correct 325 ms 2352 KB Output is correct
31 Correct 446 ms 2632 KB Output is correct
32 Correct 450 ms 2384 KB Output is correct
33 Correct 463 ms 3080 KB Output is correct
34 Correct 387 ms 2388 KB Output is correct
35 Correct 429 ms 2624 KB Output is correct
36 Correct 468 ms 2644 KB Output is correct
37 Correct 448 ms 2368 KB Output is correct
38 Correct 462 ms 2644 KB Output is correct
39 Correct 438 ms 2828 KB Output is correct
40 Correct 468 ms 2384 KB Output is correct
41 Correct 443 ms 2692 KB Output is correct
42 Correct 490 ms 2932 KB Output is correct
43 Correct 406 ms 2384 KB Output is correct
44 Correct 479 ms 2556 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 2388 KB Output is correct
2 Correct 353 ms 2416 KB Output is correct
3 Correct 274 ms 2504 KB Output is correct
4 Correct 318 ms 2440 KB Output is correct
5 Correct 278 ms 2344 KB Output is correct
6 Correct 287 ms 2600 KB Output is correct
7 Correct 281 ms 2532 KB Output is correct
8 Correct 303 ms 2388 KB Output is correct
9 Correct 299 ms 2544 KB Output is correct
10 Correct 296 ms 2896 KB Output is correct
11 Correct 311 ms 2596 KB Output is correct
12 Correct 294 ms 2388 KB Output is correct
13 Correct 300 ms 2464 KB Output is correct
14 Correct 291 ms 2384 KB Output is correct
15 Correct 304 ms 2740 KB Output is correct
16 Correct 294 ms 2576 KB Output is correct
17 Correct 306 ms 2664 KB Output is correct
18 Correct 222 ms 2308 KB Output is correct
19 Correct 1047 ms 93544 KB Output is correct
20 Correct 908 ms 92932 KB Output is correct
21 Correct 1283 ms 88176 KB Output is correct
22 Correct 1069 ms 80180 KB Output is correct
23 Correct 566 ms 7928 KB Output is correct
24 Correct 566 ms 7988 KB Output is correct
25 Correct 1341 ms 92504 KB Output is correct
26 Correct 1200 ms 92100 KB Output is correct
27 Correct 902 ms 92568 KB Output is correct
28 Correct 982 ms 92084 KB Output is correct
29 Correct 889 ms 91836 KB Output is correct
30 Correct 519 ms 8056 KB Output is correct
31 Correct 904 ms 93404 KB Output is correct
32 Correct 922 ms 86052 KB Output is correct
33 Correct 542 ms 7820 KB Output is correct
34 Correct 1014 ms 93408 KB Output is correct
35 Correct 1153 ms 71144 KB Output is correct
36 Correct 542 ms 7904 KB Output is correct
37 Correct 540 ms 7828 KB Output is correct
38 Correct 741 ms 91716 KB Output is correct
39 Correct 658 ms 93076 KB Output is correct
40 Correct 1238 ms 61388 KB Output is correct
41 Correct 1038 ms 92560 KB Output is correct
42 Correct 298 ms 91536 KB Output is correct
43 Correct 695 ms 2460 KB Output is correct
44 Correct 507 ms 2348 KB Output is correct
45 Correct 345 ms 2416 KB Output is correct
46 Correct 308 ms 2300 KB Output is correct
47 Correct 357 ms 2476 KB Output is correct
48 Correct 373 ms 2656 KB Output is correct
49 Correct 350 ms 2380 KB Output is correct
50 Correct 325 ms 2384 KB Output is correct
51 Correct 349 ms 2592 KB Output is correct
52 Correct 314 ms 2388 KB Output is correct
53 Correct 361 ms 2744 KB Output is correct
54 Correct 325 ms 2352 KB Output is correct
55 Correct 446 ms 2632 KB Output is correct
56 Correct 450 ms 2384 KB Output is correct
57 Correct 463 ms 3080 KB Output is correct
58 Correct 387 ms 2388 KB Output is correct
59 Correct 429 ms 2624 KB Output is correct
60 Correct 468 ms 2644 KB Output is correct
61 Correct 448 ms 2368 KB Output is correct
62 Correct 462 ms 2644 KB Output is correct
63 Correct 438 ms 2828 KB Output is correct
64 Correct 468 ms 2384 KB Output is correct
65 Correct 443 ms 2692 KB Output is correct
66 Correct 490 ms 2932 KB Output is correct
67 Correct 406 ms 2384 KB Output is correct
68 Correct 479 ms 2556 KB Output is correct
69 Correct 3033 ms 75984 KB Output is correct
70 Correct 2856 ms 89316 KB Output is correct
71 Correct 779 ms 7644 KB Output is correct
72 Correct 825 ms 7700 KB Output is correct
73 Correct 772 ms 7888 KB Output is correct
74 Correct 1678 ms 76816 KB Output is correct
75 Correct 757 ms 7480 KB Output is correct
76 Correct 2031 ms 90024 KB Output is correct
77 Correct 1549 ms 76996 KB Output is correct
78 Correct 782 ms 7724 KB Output is correct
79 Correct 764 ms 7904 KB Output is correct
80 Correct 2568 ms 65292 KB Output is correct
81 Correct 1133 ms 7848 KB Output is correct
82 Correct 3092 ms 89244 KB Output is correct
83 Correct 2514 ms 84620 KB Output is correct
84 Correct 1176 ms 7708 KB Output is correct
85 Correct 1197 ms 7688 KB Output is correct
86 Correct 1518 ms 68096 KB Output is correct
87 Correct 1910 ms 90336 KB Output is correct
88 Correct 1113 ms 7564 KB Output is correct
89 Correct 1722 ms 80008 KB Output is correct
90 Correct 1998 ms 89752 KB Output is correct
91 Correct 1112 ms 7844 KB Output is correct
92 Correct 2660 ms 67952 KB Output is correct
93 Correct 1161 ms 7624 KB Output is correct
94 Correct 1167 ms 7656 KB Output is correct
95 Correct 1164 ms 7580 KB Output is correct
96 Correct 696 ms 92720 KB Output is correct
97 Incorrect 456 ms 92176 KB Output isn't correct
98 Halted 0 ms 0 KB -