Submission #442464

#	Time	Username	Problem	Language	Result	Execution time	Memory
442464		JovanB	Crossing (JOI21_crossing)	C++17	100 / 100	559 ms	21392 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1000000007;
const int P = 101;
const int MAXN = 200000;

int add(int a, int b){ return (a+b)%MOD; }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int sub(int a, int b){ return add(a, MOD - b); }

map <int, bool> ima;

int ppow[MAXN+5];
int pref[MAXN+5];

int hsh(string s){
    int tp = P;
    int res = 0;
    for(int i=0; i<s.size(); i++){
        res = add(res, mul(tp, s[i] - '0' + 1));
        tp = mul(tp, P);
    }
    return res;
}

string komb(const string &a, const string &b){
    string res = "";
    for(int i=0; i<a.size(); i++){
        if(a[i] == b[i]) res += a[i];
        else res += ('0' + (3 - (a[i] - '0') - (b[i] - '0')));
    }
    return res;
}

string poc;

struct Segment{
    int val;
    char lazy;
} seg[4*MAXN+5];


void init(int node, int l, int r){
    seg[node].lazy = '5';
    if(l == r){
        seg[node].val = mul(ppow[l], poc[l-1] - '0' + 1);
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].val = add(seg[node*2].val, seg[node*2+1].val);
}

void propagate(int node, int l, int r){
    if(seg[node].lazy == '5') return;
    seg[node].val = mul(sub(pref[r], pref[l-1]), seg[node].lazy - '0' + 1);
    if(l == r){
        seg[node].lazy = '5';
        return;
    }
    seg[node*2].lazy = seg[node].lazy;
    seg[node*2+1].lazy = seg[node].lazy;
    seg[node].lazy = '5';
}

void upd(int node, int l, int r, int tl, int tr, char c){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = c;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, c);
    upd(node*2+1, mid+1, r, tl, tr, c);
    seg[node].val = add(seg[node*2].val, seg[node*2+1].val);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    ppow[0] = 1;
    pref[0] = 1;
    for(int i=1; i<=n; i++) ppow[i] = mul(ppow[i-1], P);
    for(int i=1; i<=n; i++) pref[i] = add(ppow[i], pref[i-1]);
    vector <string> strings;
    for(int i=0; i<=2; i++){
        string x;
        cin >> x;
        for(int i=0; i<n; i++){
            if(x[i] == 'J') x[i] = '0';
            else if(x[i] == 'O') x[i] = '1';
            else x[i] = '2';
        }
        strings.push_back(x);
        ima[hsh(x)] = 1;
    }
    for(int i=0; i<strings.size(); i++){
        for(int j=0; j<i; j++){
            string rs = komb(strings[i], strings[j]);
            int g = hsh(rs);
            if(!ima[g]){
                strings.push_back(rs);
                ima[g] = 1;
            }
        }
    }
    int qrs;
    cin >> qrs;
    cin >> poc;
    for(int i=0; i<n; i++){
        if(poc[i] == 'J') poc[i] = '0';
        else if(poc[i] == 'O') poc[i] = '1';
        else poc[i] = '2';
    }
    init(1, 1, n);
    if(ima[seg[1].val]) cout << "Yes\n";
    else cout << "No\n";
    while(qrs--){
        int l, r;
        char c;
        cin >> l >> r >> c;
        if(c == 'J') c = '0';
        else if(c == 'O') c = '1';
        else c = '2';
        upd(1, 1, n, l, r, c);
        if(ima[seg[1].val]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int hsh(std::string)':
Main.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
Main.cpp: In function 'std::string komb(const string&, const string&)':
Main.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0; i<a.size(); i++){
      |                  ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0; i<strings.size(); i++){
      |                  ~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51