oj.uz

Submission #894475

# Submission time Handle Problem Language Result Execution time Memory
894475 2023-12-28T10:42:58 Z ttamx Crossing (JOI21_crossing) C++14
100 / 100
 531 ms 16952 KB 
#include<bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;

using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=0x3fffffff;
const int MOD=1000000007;
// const int MOD=998244353;
const ll LINF=0x1fffffffffffffff;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

template<class T>
constexpr T binpow(T a,ll b){T res=1;for(;b>0;b>>=1,a*=a)if(b&1)res*=a;return res;}

struct mint{
    ll x;
    constexpr mint(ll x=0):x(norm(x%MOD)){}
    constexpr ll norm(ll x)const{if(x<0)x+=MOD;if(x>=MOD)x-=MOD;return x;}
    explicit constexpr operator ll()const{return x;}
    constexpr ll mul(ll a,ll b){ll res=(a*b-ll(1.l*a*b/MOD)*MOD)%MOD;if(res<0)res+=MOD;return res;}
    constexpr mint operator-()const{return mint(-x);}
    constexpr mint inv()const{return binpow(mint(*this),MOD-2);}
    constexpr mint &operator+=(const mint &rhs){x=norm(x+rhs.x);return *this;}
    constexpr mint &operator-=(const mint &rhs){x=norm(x-rhs.x);return *this;}
    constexpr mint &operator*=(const mint &rhs){x=mul(x,rhs.x);return *this;}
    constexpr mint &operator/=(const mint &rhs){x=mul(x,rhs.inv().x);return *this;}
    constexpr mint &operator++(){return *this+=1;}
    constexpr mint &operator--(){return *this-=1;}
    constexpr mint operator++(int){mint res=*this;*this+=1;return res;}
    constexpr mint operator--(int){mint res=*this;*this-=1;return res;}
    friend constexpr mint operator+(mint lhs,const mint &rhs){return lhs+=rhs;}
    friend constexpr mint operator-(mint lhs,const mint &rhs){return lhs-=rhs;}
    friend constexpr mint operator*(mint lhs,const mint &rhs){return lhs*=rhs;}
    friend constexpr mint operator/(mint lhs,const mint &rhs){return lhs/=rhs;}
    friend istream &operator>>(istream &is,mint &o){ll x{};is>>x;o=mint(x);return is;}
    friend ostream &operator<<(ostream &os,const mint &o){return os<<o.x;}
    friend constexpr bool operator==(const mint &lhs,const mint &rhs){return lhs.x==rhs.x;};
    friend constexpr bool operator!=(const mint &lhs,const mint &rhs){return lhs.x!=rhs.x;};
};
using vm = vector<mint>;
mint invmod(int x){
    static vm invs{0,1};
    for(int i=sz(invs);i<=x;i++)
        invs.push_back(-MOD/i*invs[MOD%i]);
    return invs[x];
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N=2e5+5;
const int K=1<<19;
const mint BASE=rng();

int n,q;
vi a[3];
string s;
mint pw[N],pre[N];

int get(char c){
    if(c=='J')return 0;
    if(c=='O')return 1;
    if(c=='I')return 2;
    return -1;
}

struct segtree{
    mint t[K];
    int lz[K];
    void push(int l,int r,int i){
        if(lz[i]==-1)return;
        t[i]=lz[i]*(pre[r]-pre[l-1]);
        if(l<r)lz[i*2]=lz[i*2+1]=lz[i];
        lz[i]=-1;
    }
    void build(int l,int r,int i){
        lz[i]=-1;
        if(l==r)return void(t[i]=get(s[l])*pw[l]);
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=t[i*2]+t[i*2+1];
    }
    void build(){
        build(0,n-1,1);
    }
    void update(int l,int r,int i,int x,int y,int v){
        push(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=v,push(l,r,i);
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,int y,int v){
        update(0,n-1,1,x,y,v);
    }
}st;

vi convert(const string &s){
    vi res;
    for(auto x:s)res.emplace_back(get(x));
    return res;
}

mint hsh(const vi &a){
    mint res=0;
    for(int i=0;i<n;i++)res+=a[i]*pw[i];
    return res;
}

vi cross(const vi &a,const vi &b){
    vi res(n);
    for(int i=0;i<n;i++)res[i]=(a[i]+b[i])*2%3;
    return res;
}

vm val;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    pw[0]=pre[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*BASE,pre[i]=pre[i-1]+pw[i];
    for(int i=0;i<3;i++){
        string x;
        cin >> x;
        a[i]=convert(x);
    }
    for(int i=0;i<3;i++){
        val.emplace_back(hsh(a[i]));
        val.emplace_back(hsh(cross(a[i],a[(i+1)%3])));
        val.emplace_back(hsh(cross(cross(a[i],a[(i+1)%3]),a[(i+2)%3])));
    }
    cin >> q >> s;
    st.build();
    bool ok=false;
    for(auto x:val)ok|=st.t[1]==x;
    cout << (ok?"Yes\n":"No\n");
    while(q--){
        int l,r;
        char c;
        cin >> l >> r >> c;
        l--,r--;
        st.update(l,r,get(c));
        ok=false;
        for(auto x:val)ok|=st.t[1]==x;
        cout << (ok?"Yes\n":"No\n");
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10668 KB Output is correct
2 Correct 120 ms 10952 KB Output is correct
3 Correct 130 ms 10844 KB Output is correct
4 Correct 100 ms 10752 KB Output is correct
5 Correct 87 ms 10800 KB Output is correct
6 Correct 93 ms 10648 KB Output is correct
7 Correct 86 ms 10696 KB Output is correct
8 Correct 91 ms 10796 KB Output is correct
9 Correct 92 ms 10924 KB Output is correct
10 Correct 91 ms 10832 KB Output is correct
11 Correct 93 ms 10832 KB Output is correct
12 Correct 89 ms 10712 KB Output is correct
13 Correct 111 ms 11088 KB Output is correct
14 Correct 99 ms 10720 KB Output is correct
15 Correct 106 ms 10828 KB Output is correct
16 Correct 90 ms 10832 KB Output is correct
17 Correct 97 ms 11088 KB Output is correct
18 Correct 130 ms 10884 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10668 KB Output is correct
2 Correct 120 ms 10952 KB Output is correct
3 Correct 130 ms 10844 KB Output is correct
4 Correct 100 ms 10752 KB Output is correct
5 Correct 87 ms 10800 KB Output is correct
6 Correct 93 ms 10648 KB Output is correct
7 Correct 86 ms 10696 KB Output is correct
8 Correct 91 ms 10796 KB Output is correct
9 Correct 92 ms 10924 KB Output is correct
10 Correct 91 ms 10832 KB Output is correct
11 Correct 93 ms 10832 KB Output is correct
12 Correct 89 ms 10712 KB Output is correct
13 Correct 111 ms 11088 KB Output is correct
14 Correct 99 ms 10720 KB Output is correct
15 Correct 106 ms 10828 KB Output is correct
16 Correct 90 ms 10832 KB Output is correct
17 Correct 97 ms 11088 KB Output is correct
18 Correct 130 ms 10884 KB Output is correct
19 Correct 443 ms 16952 KB Output is correct
20 Correct 486 ms 16580 KB Output is correct
21 Correct 190 ms 16436 KB Output is correct
22 Correct 211 ms 15788 KB Output is correct
23 Correct 136 ms 11856 KB Output is correct
24 Correct 153 ms 12084 KB Output is correct
25 Correct 214 ms 16576 KB Output is correct
26 Correct 222 ms 16724 KB Output is correct
27 Correct 288 ms 16672 KB Output is correct
28 Correct 287 ms 16808 KB Output is correct
29 Correct 256 ms 16476 KB Output is correct
30 Correct 179 ms 11860 KB Output is correct
31 Correct 265 ms 16640 KB Output is correct
32 Correct 274 ms 16272 KB Output is correct
33 Correct 142 ms 11864 KB Output is correct
34 Correct 309 ms 16808 KB Output is correct
35 Correct 178 ms 14988 KB Output is correct
36 Correct 134 ms 11736 KB Output is correct
37 Correct 137 ms 11856 KB Output is correct
38 Correct 431 ms 16524 KB Output is correct
39 Correct 137 ms 16816 KB Output is correct
40 Correct 203 ms 15020 KB Output is correct
41 Correct 531 ms 16928 KB Output is correct
42 Correct 64 ms 16084 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10668 KB Output is correct
2 Correct 120 ms 10952 KB Output is correct
3 Correct 130 ms 10844 KB Output is correct
4 Correct 100 ms 10752 KB Output is correct
5 Correct 87 ms 10800 KB Output is correct
6 Correct 93 ms 10648 KB Output is correct
7 Correct 86 ms 10696 KB Output is correct
8 Correct 91 ms 10796 KB Output is correct
9 Correct 92 ms 10924 KB Output is correct
10 Correct 91 ms 10832 KB Output is correct
11 Correct 93 ms 10832 KB Output is correct
12 Correct 89 ms 10712 KB Output is correct
13 Correct 111 ms 11088 KB Output is correct
14 Correct 99 ms 10720 KB Output is correct
15 Correct 106 ms 10828 KB Output is correct
16 Correct 90 ms 10832 KB Output is correct
17 Correct 97 ms 11088 KB Output is correct
18 Correct 130 ms 10884 KB Output is correct
19 Correct 115 ms 10692 KB Output is correct
20 Correct 131 ms 10832 KB Output is correct
21 Correct 90 ms 10932 KB Output is correct
22 Correct 81 ms 10752 KB Output is correct
23 Correct 104 ms 10752 KB Output is correct
24 Correct 104 ms 10840 KB Output is correct
25 Correct 91 ms 10832 KB Output is correct
26 Correct 85 ms 10684 KB Output is correct
27 Correct 98 ms 10808 KB Output is correct
28 Correct 87 ms 10580 KB Output is correct
29 Correct 106 ms 10836 KB Output is correct
30 Correct 86 ms 10576 KB Output is correct
31 Correct 90 ms 10836 KB Output is correct
32 Correct 88 ms 10832 KB Output is correct
33 Correct 94 ms 10728 KB Output is correct
34 Correct 95 ms 10588 KB Output is correct
35 Correct 90 ms 10836 KB Output is correct
36 Correct 92 ms 10832 KB Output is correct
37 Correct 97 ms 10748 KB Output is correct
38 Correct 105 ms 10896 KB Output is correct
39 Correct 96 ms 10836 KB Output is correct
40 Correct 93 ms 10832 KB Output is correct
41 Correct 98 ms 10832 KB Output is correct
42 Correct 93 ms 10908 KB Output is correct
43 Correct 88 ms 10672 KB Output is correct
44 Correct 105 ms 10800 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10668 KB Output is correct
2 Correct 120 ms 10952 KB Output is correct
3 Correct 130 ms 10844 KB Output is correct
4 Correct 100 ms 10752 KB Output is correct
5 Correct 87 ms 10800 KB Output is correct
6 Correct 93 ms 10648 KB Output is correct
7 Correct 86 ms 10696 KB Output is correct
8 Correct 91 ms 10796 KB Output is correct
9 Correct 92 ms 10924 KB Output is correct
10 Correct 91 ms 10832 KB Output is correct
11 Correct 93 ms 10832 KB Output is correct
12 Correct 89 ms 10712 KB Output is correct
13 Correct 111 ms 11088 KB Output is correct
14 Correct 99 ms 10720 KB Output is correct
15 Correct 106 ms 10828 KB Output is correct
16 Correct 90 ms 10832 KB Output is correct
17 Correct 97 ms 11088 KB Output is correct
18 Correct 130 ms 10884 KB Output is correct
19 Correct 443 ms 16952 KB Output is correct
20 Correct 486 ms 16580 KB Output is correct
21 Correct 190 ms 16436 KB Output is correct
22 Correct 211 ms 15788 KB Output is correct
23 Correct 136 ms 11856 KB Output is correct
24 Correct 153 ms 12084 KB Output is correct
25 Correct 214 ms 16576 KB Output is correct
26 Correct 222 ms 16724 KB Output is correct
27 Correct 288 ms 16672 KB Output is correct
28 Correct 287 ms 16808 KB Output is correct
29 Correct 256 ms 16476 KB Output is correct
30 Correct 179 ms 11860 KB Output is correct
31 Correct 265 ms 16640 KB Output is correct
32 Correct 274 ms 16272 KB Output is correct
33 Correct 142 ms 11864 KB Output is correct
34 Correct 309 ms 16808 KB Output is correct
35 Correct 178 ms 14988 KB Output is correct
36 Correct 134 ms 11736 KB Output is correct
37 Correct 137 ms 11856 KB Output is correct
38 Correct 431 ms 16524 KB Output is correct
39 Correct 137 ms 16816 KB Output is correct
40 Correct 203 ms 15020 KB Output is correct
41 Correct 531 ms 16928 KB Output is correct
42 Correct 64 ms 16084 KB Output is correct
43 Correct 115 ms 10692 KB Output is correct
44 Correct 131 ms 10832 KB Output is correct
45 Correct 90 ms 10932 KB Output is correct
46 Correct 81 ms 10752 KB Output is correct
47 Correct 104 ms 10752 KB Output is correct
48 Correct 104 ms 10840 KB Output is correct
49 Correct 91 ms 10832 KB Output is correct
50 Correct 85 ms 10684 KB Output is correct
51 Correct 98 ms 10808 KB Output is correct
52 Correct 87 ms 10580 KB Output is correct
53 Correct 106 ms 10836 KB Output is correct
54 Correct 86 ms 10576 KB Output is correct
55 Correct 90 ms 10836 KB Output is correct
56 Correct 88 ms 10832 KB Output is correct
57 Correct 94 ms 10728 KB Output is correct
58 Correct 95 ms 10588 KB Output is correct
59 Correct 90 ms 10836 KB Output is correct
60 Correct 92 ms 10832 KB Output is correct
61 Correct 97 ms 10748 KB Output is correct
62 Correct 105 ms 10896 KB Output is correct
63 Correct 96 ms 10836 KB Output is correct
64 Correct 93 ms 10832 KB Output is correct
65 Correct 98 ms 10832 KB Output is correct
66 Correct 93 ms 10908 KB Output is correct
67 Correct 88 ms 10672 KB Output is correct
68 Correct 105 ms 10800 KB Output is correct
69 Correct 420 ms 15500 KB Output is correct
70 Correct 511 ms 16736 KB Output is correct
71 Correct 136 ms 11840 KB Output is correct
72 Correct 135 ms 11992 KB Output is correct
73 Correct 150 ms 12172 KB Output is correct
74 Correct 183 ms 15504 KB Output is correct
75 Correct 138 ms 11860 KB Output is correct
76 Correct 207 ms 16740 KB Output is correct
77 Correct 214 ms 15792 KB Output is correct
78 Correct 134 ms 11760 KB Output is correct
79 Correct 135 ms 11968 KB Output is correct
80 Correct 212 ms 15064 KB Output is correct
81 Correct 131 ms 11856 KB Output is correct
82 Correct 196 ms 16816 KB Output is correct
83 Correct 227 ms 16232 KB Output is correct
84 Correct 134 ms 11980 KB Output is correct
85 Correct 135 ms 11768 KB Output is correct
86 Correct 288 ms 15200 KB Output is correct
87 Correct 303 ms 16772 KB Output is correct
88 Correct 174 ms 11776 KB Output is correct
89 Correct 242 ms 15944 KB Output is correct
90 Correct 262 ms 16748 KB Output is correct
91 Correct 176 ms 11860 KB Output is correct
92 Correct 203 ms 15220 KB Output is correct
93 Correct 138 ms 11780 KB Output is correct
94 Correct 148 ms 12088 KB Output is correct
95 Correct 135 ms 11816 KB Output is correct
96 Correct 418 ms 16580 KB Output is correct
97 Correct 158 ms 16764 KB Output is correct
98 Correct 194 ms 14952 KB Output is correct
99 Correct 521 ms 16812 KB Output is correct
100 Correct 79 ms 16208 KB Output is correct