답안 #1055433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055433	2024-08-12T19:21:46 Z	YassirSalama	Crossing (JOI21_crossing)	C++17	100 / 100	1841 ms	447060 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<char,int> mp;
#define all(v) v.begin(),v.end()
struct Hash {
    vector<int> v;
    int P,mod;
    const int maxn=2e5+100;
    int pref[(int)2e5+100];
    struct Node{
        int val;
        int lz;
        Node* left,*right;
        Node() : left(nullptr),right(nullptr){}
    };
    int f(int a){
        a%=mod;
        if(a<0) a+=mod;
        return a%=mod;
    }
    int sum(int l,int r){
        if(l==0) return pref[r];
        return f(pref[r]%mod-pref[l-1]%mod)%mod;
    }
    void push(Node* node,int l,int r){
        if(node->lz==0) return;
        node->val=f(node->lz*f(sum(l,r))%mod);
        if(l!=r){
            node->left->lz=node->lz;
            node->right->lz=node->lz;
        }
        node->lz=0;
    }
    void p(Node* node,int l,int r){
        push(node,l,r);
        int mid=(l+r)/2;
        if(l==r) return;
        push(node->left,l,mid);
        push(node->right,mid+1,r);
    }
    void build(Node* node,int l,int r,vector<int> &v){
        node->lz=0;
        if(l==r){
            node->val=v[l];
            return;
        }
        int mid=(l+r)/2;
        node->left=new Node();
        node->right=new Node();
        build(node->left,l,mid,v);
        build(node->right,mid+1,r,v);
        node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
    }
    void update(Node* node,int l,int r,int ql,int qr,int x){
        p(node,l,r);
        if(ql<=l&&r<=qr){
            node->lz=x;p(node,l,r);
            return;
        }
        int mid=(l+r)>>1;
        if(ql<=mid){
            update(node->left,l,mid,ql,qr,x);
        }
        if(qr>mid) update(node->right,mid+1,r,ql,qr,x);
        node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
    }
    int query(Node* node,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return node->val%mod;
        int mid=(l+r)/2;
        int ans=0;
        if(ql<=mid) ans=f(ans+query(node->left,l,mid,ql,qr)),ans%=mod;
        if(qr>mid) ans=f(ans+query(node->right,mid+1,r,ql,qr)),ans%=mod;
        return ans%mod;
    }
    vector<int> hsh(string s){
        int n=s.length();
        int c=1;
        vector<int> v(n);
        for(int i=0;i<n;i++){
            int x=mp[s[i]];
            v[i]=(x%mod*c%mod)%mod;
            c=(c%mod*P%mod)%mod;
        }
        return v;
    }
    Node* root;
    void b(string s,int p,int MOD){
        P=p;
        mod=MOD;
        v=hsh(s);
        for(int i=0;i<maxn;i++){
            pref[i]=binpow(P,i)%mod;
            if(i){
                pref[i]=f(pref[i]%mod+pref[i-1]%mod)%mod;
            }
        }
        root=new Node();
        int n=s.size();
        build(root,0,n-1,v);
    }
    int get(){
        return root->val%mod;
    }
    int binpow(int a,int b){
        int res=1;
        while(b){
            if(b&1) {
                res=(res%mod*a%mod)%mod;
            }
            a=(a%mod*a%mod)%mod;
            b>>=1;
        }
        return res;
    }
};
Hash b1,b2;
Hash a[9],b[9];

signed main(){
    mp['J']=1;mp['O']=4;mp['I']=7;
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    vector<string> v(3);
    cin>>v[0]>>v[1]>>v[2];
    auto cross = [&](string a,string b){
        string s;
        for(int i=0;i<n;i++){
            if(a[i]==b[i]) s+=a[i];
            else{
                for(auto c:"JOI")
                    if(c!=a[i]&&c!=b[i]){
                        s+=c;
                        break;
                    }
            }
        }
        return s;
    };
    set<string> s(v.begin(),v.end());
    while(true){
        bool f=false;
        set<string> ss=s;
        for(auto x:s){
            for(auto y:s){
                string t=cross(x,y);
                if(s.count(t)) continue;
                ss.insert(t);f=true;
            }
        }
        s=ss;
        if(!f) break;
    }
    v.clear();
    for(auto x:s) v.push_back(x);
    int q;
    cin>>q;
    string t;
    cin>>t;
    b1.b(t,31,1e9+7);
    b2.b(t,41,1e9+3);
    int c=v.size();
    for(int i=0;i<c;i++){
        a[i].b(v[i],31,1e9+7);
        b[i].b(v[i],41,1e9+3);
    }
    auto check = [&](){
        bool ok=true;
        for(int i=0;i<c;i++){
            if(a[i].get()==b1.get()&&b[i].get()==b2.get()) return true;
        }
        return false;
    };
    puts(check()?"Yes":"No");
    while(q--){
        int l,r;
        cin>>l>>r;
        l--,r--;
        char c;
        cin>>c;
        b1.update(b1.root,0,n-1,l,r,mp[c]);
        b2.update(b2.root,0,n-1,l,r,mp[c]);
        puts(check()?"Yes":"No");
    }
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:169:14: warning: unused variable 'ok' [-Wunused-variable]
  169 |         bool ok=true;
      |              ^~

Subtask #1

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	220 ms	8788 KB	Output is correct
2	Correct	233 ms	8792 KB	Output is correct
3	Correct	299 ms	8784 KB	Output is correct
4	Correct	213 ms	11748 KB	Output is correct
5	Correct	201 ms	11860 KB	Output is correct
6	Correct	207 ms	11860 KB	Output is correct
7	Correct	199 ms	11736 KB	Output is correct
8	Correct	200 ms	11860 KB	Output is correct
9	Correct	200 ms	11856 KB	Output is correct
10	Correct	201 ms	11860 KB	Output is correct
11	Correct	203 ms	11728 KB	Output is correct
12	Correct	198 ms	11856 KB	Output is correct
13	Correct	202 ms	11860 KB	Output is correct
14	Correct	199 ms	11852 KB	Output is correct
15	Correct	201 ms	11752 KB	Output is correct
16	Correct	204 ms	11856 KB	Output is correct
17	Correct	200 ms	11856 KB	Output is correct
18	Correct	293 ms	11852 KB	Output is correct

Subtask #2

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	220 ms	8788 KB	Output is correct
2	Correct	233 ms	8792 KB	Output is correct
3	Correct	299 ms	8784 KB	Output is correct
4	Correct	213 ms	11748 KB	Output is correct
5	Correct	201 ms	11860 KB	Output is correct
6	Correct	207 ms	11860 KB	Output is correct
7	Correct	199 ms	11736 KB	Output is correct
8	Correct	200 ms	11860 KB	Output is correct
9	Correct	200 ms	11856 KB	Output is correct
10	Correct	201 ms	11860 KB	Output is correct
11	Correct	203 ms	11728 KB	Output is correct
12	Correct	198 ms	11856 KB	Output is correct
13	Correct	202 ms	11860 KB	Output is correct
14	Correct	199 ms	11852 KB	Output is correct
15	Correct	201 ms	11752 KB	Output is correct
16	Correct	204 ms	11856 KB	Output is correct
17	Correct	200 ms	11856 KB	Output is correct
18	Correct	293 ms	11852 KB	Output is correct
19	Correct	802 ms	96364 KB	Output is correct
20	Correct	945 ms	96208 KB	Output is correct
21	Correct	402 ms	92028 KB	Output is correct
22	Correct	415 ms	82984 KB	Output is correct
23	Correct	280 ms	16980 KB	Output is correct
24	Correct	285 ms	17064 KB	Output is correct
25	Correct	430 ms	96216 KB	Output is correct
26	Correct	484 ms	96056 KB	Output is correct
27	Correct	558 ms	97236 KB	Output is correct
28	Correct	593 ms	96168 KB	Output is correct
29	Correct	541 ms	93664 KB	Output is correct
30	Correct	339 ms	16864 KB	Output is correct
31	Correct	540 ms	96212 KB	Output is correct
32	Correct	542 ms	88780 KB	Output is correct
33	Correct	295 ms	16724 KB	Output is correct
34	Correct	537 ms	96212 KB	Output is correct
35	Correct	379 ms	74732 KB	Output is correct
36	Correct	291 ms	16720 KB	Output is correct
37	Correct	282 ms	16776 KB	Output is correct
38	Correct	822 ms	95960 KB	Output is correct
39	Correct	293 ms	96216 KB	Output is correct
40	Correct	391 ms	67400 KB	Output is correct
41	Correct	1004 ms	96492 KB	Output is correct
42	Correct	184 ms	95696 KB	Output is correct

Subtask #3

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	220 ms	8788 KB	Output is correct
2	Correct	233 ms	8792 KB	Output is correct
3	Correct	299 ms	8784 KB	Output is correct
4	Correct	213 ms	11748 KB	Output is correct
5	Correct	201 ms	11860 KB	Output is correct
6	Correct	207 ms	11860 KB	Output is correct
7	Correct	199 ms	11736 KB	Output is correct
8	Correct	200 ms	11860 KB	Output is correct
9	Correct	200 ms	11856 KB	Output is correct
10	Correct	201 ms	11860 KB	Output is correct
11	Correct	203 ms	11728 KB	Output is correct
12	Correct	198 ms	11856 KB	Output is correct
13	Correct	202 ms	11860 KB	Output is correct
14	Correct	199 ms	11852 KB	Output is correct
15	Correct	201 ms	11752 KB	Output is correct
16	Correct	204 ms	11856 KB	Output is correct
17	Correct	200 ms	11856 KB	Output is correct
18	Correct	293 ms	11852 KB	Output is correct
19	Correct	631 ms	33976 KB	Output is correct
20	Correct	703 ms	33772 KB	Output is correct
21	Correct	302 ms	18252 KB	Output is correct
22	Correct	286 ms	18084 KB	Output is correct
23	Correct	296 ms	18004 KB	Output is correct
24	Correct	300 ms	18004 KB	Output is correct
25	Correct	302 ms	18000 KB	Output is correct
26	Correct	293 ms	18004 KB	Output is correct
27	Correct	303 ms	18004 KB	Output is correct
28	Correct	287 ms	18000 KB	Output is correct
29	Correct	306 ms	18004 KB	Output is correct
30	Correct	302 ms	17992 KB	Output is correct
31	Correct	602 ms	34008 KB	Output is correct
32	Correct	597 ms	33876 KB	Output is correct
33	Correct	614 ms	33992 KB	Output is correct
34	Correct	595 ms	33876 KB	Output is correct
35	Correct	623 ms	34128 KB	Output is correct
36	Correct	603 ms	33960 KB	Output is correct
37	Correct	607 ms	33996 KB	Output is correct
38	Correct	602 ms	33876 KB	Output is correct
39	Correct	601 ms	33940 KB	Output is correct
40	Correct	605 ms	34088 KB	Output is correct
41	Correct	599 ms	34076 KB	Output is correct
42	Correct	601 ms	34012 KB	Output is correct
43	Correct	606 ms	33872 KB	Output is correct
44	Correct	599 ms	34056 KB	Output is correct

Subtask #4

51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	220 ms	8788 KB	Output is correct
2	Correct	233 ms	8792 KB	Output is correct
3	Correct	299 ms	8784 KB	Output is correct
4	Correct	213 ms	11748 KB	Output is correct
5	Correct	201 ms	11860 KB	Output is correct
6	Correct	207 ms	11860 KB	Output is correct
7	Correct	199 ms	11736 KB	Output is correct
8	Correct	200 ms	11860 KB	Output is correct
9	Correct	200 ms	11856 KB	Output is correct
10	Correct	201 ms	11860 KB	Output is correct
11	Correct	203 ms	11728 KB	Output is correct
12	Correct	198 ms	11856 KB	Output is correct
13	Correct	202 ms	11860 KB	Output is correct
14	Correct	199 ms	11852 KB	Output is correct
15	Correct	201 ms	11752 KB	Output is correct
16	Correct	204 ms	11856 KB	Output is correct
17	Correct	200 ms	11856 KB	Output is correct
18	Correct	293 ms	11852 KB	Output is correct
19	Correct	802 ms	96364 KB	Output is correct
20	Correct	945 ms	96208 KB	Output is correct
21	Correct	402 ms	92028 KB	Output is correct
22	Correct	415 ms	82984 KB	Output is correct
23	Correct	280 ms	16980 KB	Output is correct
24	Correct	285 ms	17064 KB	Output is correct
25	Correct	430 ms	96216 KB	Output is correct
26	Correct	484 ms	96056 KB	Output is correct
27	Correct	558 ms	97236 KB	Output is correct
28	Correct	593 ms	96168 KB	Output is correct
29	Correct	541 ms	93664 KB	Output is correct
30	Correct	339 ms	16864 KB	Output is correct
31	Correct	540 ms	96212 KB	Output is correct
32	Correct	542 ms	88780 KB	Output is correct
33	Correct	295 ms	16724 KB	Output is correct
34	Correct	537 ms	96212 KB	Output is correct
35	Correct	379 ms	74732 KB	Output is correct
36	Correct	291 ms	16720 KB	Output is correct
37	Correct	282 ms	16776 KB	Output is correct
38	Correct	822 ms	95960 KB	Output is correct
39	Correct	293 ms	96216 KB	Output is correct
40	Correct	391 ms	67400 KB	Output is correct
41	Correct	1004 ms	96492 KB	Output is correct
42	Correct	184 ms	95696 KB	Output is correct
43	Correct	631 ms	33976 KB	Output is correct
44	Correct	703 ms	33772 KB	Output is correct
45	Correct	302 ms	18252 KB	Output is correct
46	Correct	286 ms	18084 KB	Output is correct
47	Correct	296 ms	18004 KB	Output is correct
48	Correct	300 ms	18004 KB	Output is correct
49	Correct	302 ms	18000 KB	Output is correct
50	Correct	293 ms	18004 KB	Output is correct
51	Correct	303 ms	18004 KB	Output is correct
52	Correct	287 ms	18000 KB	Output is correct
53	Correct	306 ms	18004 KB	Output is correct
54	Correct	302 ms	17992 KB	Output is correct
55	Correct	602 ms	34008 KB	Output is correct
56	Correct	597 ms	33876 KB	Output is correct
57	Correct	614 ms	33992 KB	Output is correct
58	Correct	595 ms	33876 KB	Output is correct
59	Correct	623 ms	34128 KB	Output is correct
60	Correct	603 ms	33960 KB	Output is correct
61	Correct	607 ms	33996 KB	Output is correct
62	Correct	602 ms	33876 KB	Output is correct
63	Correct	601 ms	33940 KB	Output is correct
64	Correct	605 ms	34088 KB	Output is correct
65	Correct	599 ms	34076 KB	Output is correct
66	Correct	601 ms	34012 KB	Output is correct
67	Correct	606 ms	33872 KB	Output is correct
68	Correct	599 ms	34056 KB	Output is correct
69	Correct	1460 ms	379476 KB	Output is correct
70	Correct	1841 ms	446728 KB	Output is correct
71	Correct	392 ms	27328 KB	Output is correct
72	Correct	386 ms	27600 KB	Output is correct
73	Correct	386 ms	27472 KB	Output is correct
74	Correct	542 ms	156936 KB	Output is correct
75	Correct	386 ms	27220 KB	Output is correct
76	Correct	611 ms	184540 KB	Output is correct
77	Correct	576 ms	157060 KB	Output is correct
78	Correct	391 ms	27212 KB	Output is correct
79	Correct	387 ms	27216 KB	Output is correct
80	Correct	1114 ms	328040 KB	Output is correct
81	Correct	718 ms	55124 KB	Output is correct
82	Correct	1324 ms	447032 KB	Output is correct
83	Correct	1239 ms	422020 KB	Output is correct
84	Correct	708 ms	55360 KB	Output is correct
85	Correct	703 ms	55336 KB	Output is correct
86	Correct	1180 ms	347780 KB	Output is correct
87	Correct	1287 ms	446936 KB	Output is correct
88	Correct	774 ms	55920 KB	Output is correct
89	Correct	1163 ms	397732 KB	Output is correct
90	Correct	1238 ms	447016 KB	Output is correct
91	Correct	763 ms	55332 KB	Output is correct
92	Correct	1095 ms	342684 KB	Output is correct
93	Correct	714 ms	55124 KB	Output is correct
94	Correct	702 ms	55100 KB	Output is correct
95	Correct	708 ms	55632 KB	Output is correct
96	Correct	819 ms	99004 KB	Output is correct
97	Correct	1000 ms	446972 KB	Output is correct
98	Correct	1088 ms	305100 KB	Output is correct
99	Correct	1773 ms	447060 KB	Output is correct
100	Correct	992 ms	446448 KB	Output is correct