oj.uz

Submission #846806

# Submission time Handle Problem Language Result Execution time Memory
846806 2023-09-08T13:20:31 Z Abito Crossing (JOI21_crossing) C++17
26 / 100
 158 ms 15380 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=2e5+5;
int n,seg[4*N+5],q,po[N],pj[N],pi[N];
char a[N],b[N],lazy[4*N+5];
int build(int node,int l,int r){
    lazy[node]='A';
    if (l==r) return seg[node]=(a[l]==b[l]);
    int mid=(l+r)/2;
    return seg[node]=build(node*2,l,mid)+build(node*2+1,mid+1,r);
}
int edit(int node,int l,int r,int lx,int rx,char x){
    if (r<lx || l>rx){
        if (lazy[node]!='A'){
            if (lazy[node]=='O') seg[node]=po[r]-po[l-1];
            elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1];
            else seg[node]=pi[r]-pi[l-1];
        }return seg[node];
    }
    if (l>=lx && r<=rx){
        lazy[node]=x;
        if (lazy[node]=='O') seg[node]=po[r]-po[l-1];
        elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1];
        else seg[node]=pi[r]-pi[l-1];
        return seg[node];
    }int mid=(l+r)/2;
    if (lazy[node]!='A'){
        lazy[node*2]=lazy[node];
        lazy[node*2+1]=lazy[node];
        lazy[node]='A';
    }return seg[node]=edit(node*2,l,mid,lx,rx,x)+edit(node*2+1,mid+1,r,lx,rx,x);
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for (int i=0;i<3;i++) for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++){
        po[i]=po[i-1],pj[i]=pj[i-1],pi[i]=pi[i-1];
        if (a[i]=='J') pj[i]++;
        elif (a[i]=='O') po[i]++;
        else pi[i]++;
    }
    cin>>q;
    for (int i=1;i<=n;i++) cin>>b[i];
    build(1,1,n);
    if (seg[1]==n) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    while (q--){
        int l,r;char x;cin>>l>>r>>x;
        edit(1,1,n,l,r,x);
        if (seg[1]==n) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3024 KB Output is correct
2 Correct 59 ms 2900 KB Output is correct
3 Correct 53 ms 2900 KB Output is correct
4 Correct 49 ms 2884 KB Output is correct
5 Correct 50 ms 2856 KB Output is correct
6 Correct 49 ms 3064 KB Output is correct
7 Correct 50 ms 2892 KB Output is correct
8 Correct 52 ms 3020 KB Output is correct
9 Correct 52 ms 3004 KB Output is correct
10 Correct 55 ms 3056 KB Output is correct
11 Correct 52 ms 2900 KB Output is correct
12 Correct 52 ms 2908 KB Output is correct
13 Correct 53 ms 3004 KB Output is correct
14 Correct 56 ms 2896 KB Output is correct
15 Correct 53 ms 3084 KB Output is correct
16 Correct 54 ms 3028 KB Output is correct
17 Correct 54 ms 3076 KB Output is correct
18 Correct 50 ms 2940 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3024 KB Output is correct
2 Correct 59 ms 2900 KB Output is correct
3 Correct 53 ms 2900 KB Output is correct
4 Correct 49 ms 2884 KB Output is correct
5 Correct 50 ms 2856 KB Output is correct
6 Correct 49 ms 3064 KB Output is correct
7 Correct 50 ms 2892 KB Output is correct
8 Correct 52 ms 3020 KB Output is correct
9 Correct 52 ms 3004 KB Output is correct
10 Correct 55 ms 3056 KB Output is correct
11 Correct 52 ms 2900 KB Output is correct
12 Correct 52 ms 2908 KB Output is correct
13 Correct 53 ms 3004 KB Output is correct
14 Correct 56 ms 2896 KB Output is correct
15 Correct 53 ms 3084 KB Output is correct
16 Correct 54 ms 3028 KB Output is correct
17 Correct 54 ms 3076 KB Output is correct
18 Correct 50 ms 2940 KB Output is correct
19 Correct 153 ms 11904 KB Output is correct
20 Correct 137 ms 13480 KB Output is correct
21 Correct 112 ms 14488 KB Output is correct
22 Correct 97 ms 13896 KB Output is correct
23 Correct 83 ms 5684 KB Output is correct
24 Correct 80 ms 5720 KB Output is correct
25 Correct 106 ms 15168 KB Output is correct
26 Correct 122 ms 15236 KB Output is correct
27 Correct 132 ms 14956 KB Output is correct
28 Correct 125 ms 15180 KB Output is correct
29 Correct 116 ms 14912 KB Output is correct
30 Correct 91 ms 5904 KB Output is correct
31 Correct 119 ms 14924 KB Output is correct
32 Correct 117 ms 14336 KB Output is correct
33 Correct 77 ms 5800 KB Output is correct
34 Correct 126 ms 15160 KB Output is correct
35 Correct 99 ms 13288 KB Output is correct
36 Correct 76 ms 5716 KB Output is correct
37 Correct 77 ms 5700 KB Output is correct
38 Correct 137 ms 14960 KB Output is correct
39 Correct 85 ms 15204 KB Output is correct
40 Correct 95 ms 11148 KB Output is correct
41 Correct 158 ms 15380 KB Output is correct
42 Correct 42 ms 14600 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3024 KB Output is correct
2 Correct 59 ms 2900 KB Output is correct
3 Correct 53 ms 2900 KB Output is correct
4 Correct 49 ms 2884 KB Output is correct
5 Correct 50 ms 2856 KB Output is correct
6 Correct 49 ms 3064 KB Output is correct
7 Correct 50 ms 2892 KB Output is correct
8 Correct 52 ms 3020 KB Output is correct
9 Correct 52 ms 3004 KB Output is correct
10 Correct 55 ms 3056 KB Output is correct
11 Correct 52 ms 2900 KB Output is correct
12 Correct 52 ms 2908 KB Output is correct
13 Correct 53 ms 3004 KB Output is correct
14 Correct 56 ms 2896 KB Output is correct
15 Correct 53 ms 3084 KB Output is correct
16 Correct 54 ms 3028 KB Output is correct
17 Correct 54 ms 3076 KB Output is correct
18 Correct 50 ms 2940 KB Output is correct
19 Correct 57 ms 2908 KB Output is correct
20 Correct 52 ms 2900 KB Output is correct
21 Incorrect 53 ms 2896 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3024 KB Output is correct
2 Correct 59 ms 2900 KB Output is correct
3 Correct 53 ms 2900 KB Output is correct
4 Correct 49 ms 2884 KB Output is correct
5 Correct 50 ms 2856 KB Output is correct
6 Correct 49 ms 3064 KB Output is correct
7 Correct 50 ms 2892 KB Output is correct
8 Correct 52 ms 3020 KB Output is correct
9 Correct 52 ms 3004 KB Output is correct
10 Correct 55 ms 3056 KB Output is correct
11 Correct 52 ms 2900 KB Output is correct
12 Correct 52 ms 2908 KB Output is correct
13 Correct 53 ms 3004 KB Output is correct
14 Correct 56 ms 2896 KB Output is correct
15 Correct 53 ms 3084 KB Output is correct
16 Correct 54 ms 3028 KB Output is correct
17 Correct 54 ms 3076 KB Output is correct
18 Correct 50 ms 2940 KB Output is correct
19 Correct 153 ms 11904 KB Output is correct
20 Correct 137 ms 13480 KB Output is correct
21 Correct 112 ms 14488 KB Output is correct
22 Correct 97 ms 13896 KB Output is correct
23 Correct 83 ms 5684 KB Output is correct
24 Correct 80 ms 5720 KB Output is correct
25 Correct 106 ms 15168 KB Output is correct
26 Correct 122 ms 15236 KB Output is correct
27 Correct 132 ms 14956 KB Output is correct
28 Correct 125 ms 15180 KB Output is correct
29 Correct 116 ms 14912 KB Output is correct
30 Correct 91 ms 5904 KB Output is correct
31 Correct 119 ms 14924 KB Output is correct
32 Correct 117 ms 14336 KB Output is correct
33 Correct 77 ms 5800 KB Output is correct
34 Correct 126 ms 15160 KB Output is correct
35 Correct 99 ms 13288 KB Output is correct
36 Correct 76 ms 5716 KB Output is correct
37 Correct 77 ms 5700 KB Output is correct
38 Correct 137 ms 14960 KB Output is correct
39 Correct 85 ms 15204 KB Output is correct
40 Correct 95 ms 11148 KB Output is correct
41 Correct 158 ms 15380 KB Output is correct
42 Correct 42 ms 14600 KB Output is correct
43 Correct 57 ms 2908 KB Output is correct
44 Correct 52 ms 2900 KB Output is correct
45 Incorrect 53 ms 2896 KB Output isn't correct
46 Halted 0 ms 0 KB -