oj.uz

Submission #661760

# Submission time Handle Problem Language Result Execution time Memory
661760 2022-11-26T04:42:03 Z Darren0724 Crossing (JOI21_crossing) C++17
100 / 100
 686 ms 31636 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
int k=29;
const int mod=1e9+7;
vector<int> pw;
vector<int> pw1;
struct seg{
    int l,m,r,lz=0,val=0;
    seg *lc,*rc;
    seg(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new seg(l,m);
        rc=new seg(m,r);
    }
    int rv(){
        if(lz!=0){
            return lz*pw1[r-l-1]%mod;
        }
        return val;
    }
    void pull(){
        val=lc->rv()+rc->rv()*pw[m-l];
        val%=mod;
    }
    void push(){
        if(lz!=0){
            lc->lz=lz;
            rc->lz=lz;
            lz=0;
        }
    }
    void upd(int a,int b,int p){
        if(a<=l&&b>=r){
            lz=p;
            return;
        }
        push();
        if(a<m){
            lc->upd(a,b,p);
        }
        if(b>m){
            rc->upd(a,b,p);
        }
        pull();
    }
};
string comb(string &a,string &b){
    int n=a.size();
    string ans="";
    for(int i=0;i<n;i++){
        if(a[i]==b[i]){
            ans+=a[i];
        }
        else{
            if(a[i]!='J'&&b[i]!='J'){
                ans+='J';
            }
            if(a[i]!='O'&&b[i]!='O'){
                ans+='O';
            }
            if(a[i]!='I'&&b[i]!='I'){
                ans+='I';
            }
        }
    }
    return ans;
}
int get_hash(string &s){
    int ans=0;
    int n=s.size();
    for(int i=n-1;i>=0;i--){
        ans=ans*k+s[i]-'A';
        ans%=mod;
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    pw.resize(n+1);
    pw1.resize(n+1);
    pw[0]=1;
    pw1[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=(pw[i-1]*k)%mod;
        pw1[i]=pw1[i-1]+pw[i];
        pw1[i]%=mod;
    }
    vector<string> s(9);
    vector<int> v(9);
    for(int i=0;i<3;i++){
        cin>>s[i];
    }
    s[3]=comb(s[0],s[1]);
    s[4]=comb(s[0],s[2]);
    s[5]=comb(s[1],s[2]);
    s[6]=comb(s[5],s[0]);
    s[7]=comb(s[4],s[1]);
    s[8]=comb(s[3],s[2]);
    for(int i=0;i<9;i++){
        v[i]=get_hash(s[i]);
    }
    int q;cin>>q;
    string str;cin>>str;
    seg *rt=new seg(0,n);
    for(int i=0;i<n;i++){
        rt->upd(i,i+1,str[i]-'A');
    }
    int ans=rt->rv();
    bool flag=0;
    for(int j=0;j<9;j++){
        if(ans==v[j]){
            flag=1;
        }
    }
    if(flag){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        char c;cin>>c;
        rt->upd(a-1,b,c-'A');
        int ans=rt->rv();
        bool flag=0;
        for(int j=0;j<9;j++){
            if(ans==v[j]){
                flag=1;
            }
        }
        if(flag){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }


    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 972 KB Output is correct
2 Correct 284 ms 1020 KB Output is correct
3 Correct 285 ms 984 KB Output is correct
4 Correct 268 ms 1112 KB Output is correct
5 Correct 279 ms 1140 KB Output is correct
6 Correct 265 ms 984 KB Output is correct
7 Correct 277 ms 972 KB Output is correct
8 Correct 290 ms 924 KB Output is correct
9 Correct 290 ms 1012 KB Output is correct
10 Correct 282 ms 1020 KB Output is correct
11 Correct 286 ms 960 KB Output is correct
12 Correct 277 ms 984 KB Output is correct
13 Correct 293 ms 1024 KB Output is correct
14 Correct 301 ms 1040 KB Output is correct
15 Correct 279 ms 1012 KB Output is correct
16 Correct 279 ms 972 KB Output is correct
17 Correct 284 ms 1100 KB Output is correct
18 Correct 291 ms 1008 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 972 KB Output is correct
2 Correct 284 ms 1020 KB Output is correct
3 Correct 285 ms 984 KB Output is correct
4 Correct 268 ms 1112 KB Output is correct
5 Correct 279 ms 1140 KB Output is correct
6 Correct 265 ms 984 KB Output is correct
7 Correct 277 ms 972 KB Output is correct
8 Correct 290 ms 924 KB Output is correct
9 Correct 290 ms 1012 KB Output is correct
10 Correct 282 ms 1020 KB Output is correct
11 Correct 286 ms 960 KB Output is correct
12 Correct 277 ms 984 KB Output is correct
13 Correct 293 ms 1024 KB Output is correct
14 Correct 301 ms 1040 KB Output is correct
15 Correct 279 ms 1012 KB Output is correct
16 Correct 279 ms 972 KB Output is correct
17 Correct 284 ms 1100 KB Output is correct
18 Correct 291 ms 1008 KB Output is correct
19 Correct 562 ms 31344 KB Output is correct
20 Correct 540 ms 31260 KB Output is correct
21 Correct 454 ms 29504 KB Output is correct
22 Correct 449 ms 26600 KB Output is correct
23 Correct 431 ms 2632 KB Output is correct
24 Correct 363 ms 2512 KB Output is correct
25 Correct 518 ms 31392 KB Output is correct
26 Correct 504 ms 31236 KB Output is correct
27 Correct 533 ms 31264 KB Output is correct
28 Correct 554 ms 31384 KB Output is correct
29 Correct 553 ms 30348 KB Output is correct
30 Correct 332 ms 2720 KB Output is correct
31 Correct 524 ms 31332 KB Output is correct
32 Correct 517 ms 28592 KB Output is correct
33 Correct 324 ms 2508 KB Output is correct
34 Correct 514 ms 31268 KB Output is correct
35 Correct 428 ms 23476 KB Output is correct
36 Correct 323 ms 2712 KB Output is correct
37 Correct 318 ms 2712 KB Output is correct
38 Correct 460 ms 31264 KB Output is correct
39 Correct 391 ms 31380 KB Output is correct
40 Correct 466 ms 21048 KB Output is correct
41 Correct 614 ms 31636 KB Output is correct
42 Correct 330 ms 31476 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 972 KB Output is correct
2 Correct 284 ms 1020 KB Output is correct
3 Correct 285 ms 984 KB Output is correct
4 Correct 268 ms 1112 KB Output is correct
5 Correct 279 ms 1140 KB Output is correct
6 Correct 265 ms 984 KB Output is correct
7 Correct 277 ms 972 KB Output is correct
8 Correct 290 ms 924 KB Output is correct
9 Correct 290 ms 1012 KB Output is correct
10 Correct 282 ms 1020 KB Output is correct
11 Correct 286 ms 960 KB Output is correct
12 Correct 277 ms 984 KB Output is correct
13 Correct 293 ms 1024 KB Output is correct
14 Correct 301 ms 1040 KB Output is correct
15 Correct 279 ms 1012 KB Output is correct
16 Correct 279 ms 972 KB Output is correct
17 Correct 284 ms 1100 KB Output is correct
18 Correct 291 ms 1008 KB Output is correct
19 Correct 278 ms 1140 KB Output is correct
20 Correct 281 ms 1172 KB Output is correct
21 Correct 279 ms 1176 KB Output is correct
22 Correct 263 ms 1144 KB Output is correct
23 Correct 283 ms 1204 KB Output is correct
24 Correct 275 ms 1112 KB Output is correct
25 Correct 283 ms 1060 KB Output is correct
26 Correct 283 ms 1148 KB Output is correct
27 Correct 282 ms 1136 KB Output is correct
28 Correct 256 ms 1008 KB Output is correct
29 Correct 288 ms 1144 KB Output is correct
30 Correct 275 ms 1204 KB Output is correct
31 Correct 281 ms 1060 KB Output is correct
32 Correct 278 ms 1212 KB Output is correct
33 Correct 286 ms 1136 KB Output is correct
34 Correct 264 ms 1224 KB Output is correct
35 Correct 281 ms 1084 KB Output is correct
36 Correct 280 ms 1200 KB Output is correct
37 Correct 287 ms 1100 KB Output is correct
38 Correct 279 ms 1140 KB Output is correct
39 Correct 285 ms 1168 KB Output is correct
40 Correct 277 ms 1172 KB Output is correct
41 Correct 281 ms 1272 KB Output is correct
42 Correct 283 ms 1100 KB Output is correct
43 Correct 274 ms 1264 KB Output is correct
44 Correct 285 ms 1104 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 972 KB Output is correct
2 Correct 284 ms 1020 KB Output is correct
3 Correct 285 ms 984 KB Output is correct
4 Correct 268 ms 1112 KB Output is correct
5 Correct 279 ms 1140 KB Output is correct
6 Correct 265 ms 984 KB Output is correct
7 Correct 277 ms 972 KB Output is correct
8 Correct 290 ms 924 KB Output is correct
9 Correct 290 ms 1012 KB Output is correct
10 Correct 282 ms 1020 KB Output is correct
11 Correct 286 ms 960 KB Output is correct
12 Correct 277 ms 984 KB Output is correct
13 Correct 293 ms 1024 KB Output is correct
14 Correct 301 ms 1040 KB Output is correct
15 Correct 279 ms 1012 KB Output is correct
16 Correct 279 ms 972 KB Output is correct
17 Correct 284 ms 1100 KB Output is correct
18 Correct 291 ms 1008 KB Output is correct
19 Correct 562 ms 31344 KB Output is correct
20 Correct 540 ms 31260 KB Output is correct
21 Correct 454 ms 29504 KB Output is correct
22 Correct 449 ms 26600 KB Output is correct
23 Correct 431 ms 2632 KB Output is correct
24 Correct 363 ms 2512 KB Output is correct
25 Correct 518 ms 31392 KB Output is correct
26 Correct 504 ms 31236 KB Output is correct
27 Correct 533 ms 31264 KB Output is correct
28 Correct 554 ms 31384 KB Output is correct
29 Correct 553 ms 30348 KB Output is correct
30 Correct 332 ms 2720 KB Output is correct
31 Correct 524 ms 31332 KB Output is correct
32 Correct 517 ms 28592 KB Output is correct
33 Correct 324 ms 2508 KB Output is correct
34 Correct 514 ms 31268 KB Output is correct
35 Correct 428 ms 23476 KB Output is correct
36 Correct 323 ms 2712 KB Output is correct
37 Correct 318 ms 2712 KB Output is correct
38 Correct 460 ms 31264 KB Output is correct
39 Correct 391 ms 31380 KB Output is correct
40 Correct 466 ms 21048 KB Output is correct
41 Correct 614 ms 31636 KB Output is correct
42 Correct 330 ms 31476 KB Output is correct
43 Correct 278 ms 1140 KB Output is correct
44 Correct 281 ms 1172 KB Output is correct
45 Correct 279 ms 1176 KB Output is correct
46 Correct 263 ms 1144 KB Output is correct
47 Correct 283 ms 1204 KB Output is correct
48 Correct 275 ms 1112 KB Output is correct
49 Correct 283 ms 1060 KB Output is correct
50 Correct 283 ms 1148 KB Output is correct
51 Correct 282 ms 1136 KB Output is correct
52 Correct 256 ms 1008 KB Output is correct
53 Correct 288 ms 1144 KB Output is correct
54 Correct 275 ms 1204 KB Output is correct
55 Correct 281 ms 1060 KB Output is correct
56 Correct 278 ms 1212 KB Output is correct
57 Correct 286 ms 1136 KB Output is correct
58 Correct 264 ms 1224 KB Output is correct
59 Correct 281 ms 1084 KB Output is correct
60 Correct 280 ms 1200 KB Output is correct
61 Correct 287 ms 1100 KB Output is correct
62 Correct 279 ms 1140 KB Output is correct
63 Correct 285 ms 1168 KB Output is correct
64 Correct 277 ms 1172 KB Output is correct
65 Correct 281 ms 1272 KB Output is correct
66 Correct 283 ms 1100 KB Output is correct
67 Correct 274 ms 1264 KB Output is correct
68 Correct 285 ms 1104 KB Output is correct
69 Correct 506 ms 26408 KB Output is correct
70 Correct 502 ms 31380 KB Output is correct
71 Correct 320 ms 2732 KB Output is correct
72 Correct 319 ms 2668 KB Output is correct
73 Correct 314 ms 2692 KB Output is correct
74 Correct 435 ms 26288 KB Output is correct
75 Correct 321 ms 2644 KB Output is correct
76 Correct 477 ms 31248 KB Output is correct
77 Correct 459 ms 26320 KB Output is correct
78 Correct 324 ms 2828 KB Output is correct
79 Correct 324 ms 2652 KB Output is correct
80 Correct 426 ms 22576 KB Output is correct
81 Correct 328 ms 2688 KB Output is correct
82 Correct 485 ms 31360 KB Output is correct
83 Correct 473 ms 29528 KB Output is correct
84 Correct 321 ms 2672 KB Output is correct
85 Correct 319 ms 2764 KB Output is correct
86 Correct 479 ms 24072 KB Output is correct
87 Correct 561 ms 31552 KB Output is correct
88 Correct 340 ms 2924 KB Output is correct
89 Correct 480 ms 27732 KB Output is correct
90 Correct 519 ms 31324 KB Output is correct
91 Correct 329 ms 2636 KB Output is correct
92 Correct 443 ms 23588 KB Output is correct
93 Correct 334 ms 2704 KB Output is correct
94 Correct 331 ms 2708 KB Output is correct
95 Correct 332 ms 2704 KB Output is correct
96 Correct 506 ms 31416 KB Output is correct
97 Correct 445 ms 31328 KB Output is correct
98 Correct 487 ms 20880 KB Output is correct
99 Correct 686 ms 31560 KB Output is correct
100 Correct 382 ms 31488 KB Output is correct