oj.uz

Submission #423394

# Submission time Handle Problem Language Result Execution time Memory
423394 2021-06-11T05:05:27 Z 최서현(#7497) Crossing (JOI21_crossing) C++17
26 / 100
 305 ms 4380 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <string>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;

using namespace std;

int nxt[202020];
string a, b, c, d;

struct Node
{
    char c;
    bool con, val;
}seg[808080];

void prop(int ind, int s, int e)
{
    if(seg[ind].con)
    {
        int x = ind << 1, y = ind << 1 | 1;
        seg[x].con = seg[y].con = true;
        seg[x].c = seg[y].c = seg[ind].c;

        int mid = s + e >> 1;
        seg[x].val = (a[s] == seg[x].c && nxt[s] >= mid);
        seg[y].val = (a[mid] == seg[y].c && nxt[mid] >= e);
    }
}

void mrge(int ind)
{
    Node &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1];
    if(x.con && y.con && x.c == y.c) nd.c = x.c, nd.con = true;
    else nd.con = false;
    nd.val = (x.val && y.val);
}

void init(int ind, int s, int e)
{
    if(s + 1 == e)
    {
        seg[ind].c = d[s];
        seg[ind].con = true;
        seg[ind].val = (a[s] == d[s]);
        return;
    }

    int mid = s + e >> 1;
    init(ind << 1, s, mid);
    init(ind << 1 | 1, mid, e);
    mrge(ind);
}

void upd(int ind, int s, int e, int l, int r, char c)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].con = true;
        seg[ind].c = c;
        seg[ind].val = (a[s] == seg[ind].c && nxt[s] >= e);
        return;
    }

    prop(ind, s, e);
    int mid = s + e >> 1;
    upd(ind << 1, s, mid, l, r, c);
    upd(ind << 1 | 1, mid, e, l, r, c);
    mrge(ind);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    cin >> a >> b >> c;
    int pr = 0;
    for(int i = 1; i < n; ++i)
    {
        if(a[pr] != a[i])
        {
            for(int j = pr; j < i; ++j) nxt[j] = i;
            pr = i;
        }
    }
    for(int j = pr; j < n; ++j) nxt[j] = n;

    int T; cin >> T >> d;
    init(1, 0, n);
    cout << (seg[1].val ? "Yes\n" : "No\n");

    while(T--)
    {
        int l, r; char c; cin >> l >> r >> c; --l;
        upd(1, 0, n, l, r, c);
        cout << (seg[1].val ? "Yes\n" : "No\n");
    }
}

Compilation message

Main.cpp: In function 'void prop(int, int, int)':
Main.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In function 'void init(int, int, int)':
Main.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, char)':
Main.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 832 KB Output is correct
2 Correct 100 ms 824 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 79 ms 824 KB Output is correct
5 Correct 98 ms 832 KB Output is correct
6 Correct 81 ms 964 KB Output is correct
7 Correct 84 ms 828 KB Output is correct
8 Correct 83 ms 808 KB Output is correct
9 Correct 85 ms 860 KB Output is correct
10 Correct 95 ms 964 KB Output is correct
11 Correct 86 ms 872 KB Output is correct
12 Correct 89 ms 816 KB Output is correct
13 Correct 87 ms 808 KB Output is correct
14 Correct 83 ms 896 KB Output is correct
15 Correct 96 ms 840 KB Output is correct
16 Correct 95 ms 872 KB Output is correct
17 Correct 84 ms 1032 KB Output is correct
18 Correct 87 ms 824 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 832 KB Output is correct
2 Correct 100 ms 824 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 79 ms 824 KB Output is correct
5 Correct 98 ms 832 KB Output is correct
6 Correct 81 ms 964 KB Output is correct
7 Correct 84 ms 828 KB Output is correct
8 Correct 83 ms 808 KB Output is correct
9 Correct 85 ms 860 KB Output is correct
10 Correct 95 ms 964 KB Output is correct
11 Correct 86 ms 872 KB Output is correct
12 Correct 89 ms 816 KB Output is correct
13 Correct 87 ms 808 KB Output is correct
14 Correct 83 ms 896 KB Output is correct
15 Correct 96 ms 840 KB Output is correct
16 Correct 95 ms 872 KB Output is correct
17 Correct 84 ms 1032 KB Output is correct
18 Correct 87 ms 824 KB Output is correct
19 Correct 269 ms 4252 KB Output is correct
20 Correct 305 ms 4056 KB Output is correct
21 Correct 170 ms 3916 KB Output is correct
22 Correct 167 ms 3912 KB Output is correct
23 Correct 129 ms 1024 KB Output is correct
24 Correct 134 ms 1032 KB Output is correct
25 Correct 180 ms 4116 KB Output is correct
26 Correct 196 ms 4108 KB Output is correct
27 Correct 211 ms 4256 KB Output is correct
28 Correct 234 ms 4108 KB Output is correct
29 Correct 245 ms 4108 KB Output is correct
30 Correct 153 ms 1028 KB Output is correct
31 Correct 214 ms 4036 KB Output is correct
32 Correct 198 ms 3984 KB Output is correct
33 Correct 135 ms 1056 KB Output is correct
34 Correct 208 ms 4116 KB Output is correct
35 Correct 162 ms 3700 KB Output is correct
36 Correct 131 ms 1168 KB Output is correct
37 Correct 132 ms 1032 KB Output is correct
38 Correct 215 ms 4140 KB Output is correct
39 Correct 142 ms 4296 KB Output is correct
40 Correct 159 ms 2848 KB Output is correct
41 Correct 269 ms 4256 KB Output is correct
42 Correct 61 ms 4380 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 832 KB Output is correct
2 Correct 100 ms 824 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 79 ms 824 KB Output is correct
5 Correct 98 ms 832 KB Output is correct
6 Correct 81 ms 964 KB Output is correct
7 Correct 84 ms 828 KB Output is correct
8 Correct 83 ms 808 KB Output is correct
9 Correct 85 ms 860 KB Output is correct
10 Correct 95 ms 964 KB Output is correct
11 Correct 86 ms 872 KB Output is correct
12 Correct 89 ms 816 KB Output is correct
13 Correct 87 ms 808 KB Output is correct
14 Correct 83 ms 896 KB Output is correct
15 Correct 96 ms 840 KB Output is correct
16 Correct 95 ms 872 KB Output is correct
17 Correct 84 ms 1032 KB Output is correct
18 Correct 87 ms 824 KB Output is correct
19 Correct 94 ms 768 KB Output is correct
20 Correct 92 ms 828 KB Output is correct
21 Incorrect 83 ms 836 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 832 KB Output is correct
2 Correct 100 ms 824 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 79 ms 824 KB Output is correct
5 Correct 98 ms 832 KB Output is correct
6 Correct 81 ms 964 KB Output is correct
7 Correct 84 ms 828 KB Output is correct
8 Correct 83 ms 808 KB Output is correct
9 Correct 85 ms 860 KB Output is correct
10 Correct 95 ms 964 KB Output is correct
11 Correct 86 ms 872 KB Output is correct
12 Correct 89 ms 816 KB Output is correct
13 Correct 87 ms 808 KB Output is correct
14 Correct 83 ms 896 KB Output is correct
15 Correct 96 ms 840 KB Output is correct
16 Correct 95 ms 872 KB Output is correct
17 Correct 84 ms 1032 KB Output is correct
18 Correct 87 ms 824 KB Output is correct
19 Correct 269 ms 4252 KB Output is correct
20 Correct 305 ms 4056 KB Output is correct
21 Correct 170 ms 3916 KB Output is correct
22 Correct 167 ms 3912 KB Output is correct
23 Correct 129 ms 1024 KB Output is correct
24 Correct 134 ms 1032 KB Output is correct
25 Correct 180 ms 4116 KB Output is correct
26 Correct 196 ms 4108 KB Output is correct
27 Correct 211 ms 4256 KB Output is correct
28 Correct 234 ms 4108 KB Output is correct
29 Correct 245 ms 4108 KB Output is correct
30 Correct 153 ms 1028 KB Output is correct
31 Correct 214 ms 4036 KB Output is correct
32 Correct 198 ms 3984 KB Output is correct
33 Correct 135 ms 1056 KB Output is correct
34 Correct 208 ms 4116 KB Output is correct
35 Correct 162 ms 3700 KB Output is correct
36 Correct 131 ms 1168 KB Output is correct
37 Correct 132 ms 1032 KB Output is correct
38 Correct 215 ms 4140 KB Output is correct
39 Correct 142 ms 4296 KB Output is correct
40 Correct 159 ms 2848 KB Output is correct
41 Correct 269 ms 4256 KB Output is correct
42 Correct 61 ms 4380 KB Output is correct
43 Correct 94 ms 768 KB Output is correct
44 Correct 92 ms 828 KB Output is correct
45 Incorrect 83 ms 836 KB Output isn't correct
46 Halted 0 ms 0 KB -