oj.uz

Submission #771165

# Submission time Handle Problem Language Result Execution time Memory
771165 2023-07-02T14:01:25 Z Sam_a17 Crossing (JOI21_crossing) C++17
26 / 100
 306 ms 37612 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long

void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
// template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(Tree <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 

// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  } else if(str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
const long long mod = 1e9 + 7;


long long add(long long a, long long b) {
  return (a + b) % mod;
}

long long sub(long long a, long long b) {
  return (a - b) % mod;
}

long long mult(long long a, long long b) {
  return (a * b) % mod;
}


const int N = 2e5 + 10;
int n;
string s[3];

long long hi1[4][N];
long long hi2[4][N];

long long h1[N], h2[N];
long long pw1[N], pw2[N];
 

struct segTree {
  struct node {
    pair<long long, long long> value;
    int sz;
    long long  lazy;
  };
  vector<node> tree;
  int size = 1;
 
  void propagate(int x, int lx, int rx) {
    if(rx - lx == 1 || tree[x].lazy == -1) {
      return;
    }
 
    int mid = (lx + rx) / 2;
    tree[2 * x + 1].lazy = tree[x].lazy;
    int sz = tree[2 * x + 1].sz;
    tree[2 * x + 1].value = {hi1[tree[x].lazy][sz], hi2[tree[x].lazy][sz]};
 
    tree[2 * x + 2].lazy = tree[x].lazy;
    sz = tree[2 * x + 2].sz;
    tree[2 * x + 2].value = {hi1[tree[x].lazy][sz], hi2[tree[x].lazy][sz]};
 
    tree[x].lazy = -1;
  }

  node merge(node a, node b) {
    auto first = a;
    auto second = b;
    int sz2 = a.sz;

    second.value.first = mult(second.value.first, pw1[sz2]);
    second.value.second = mult(second.value.second, pw2[sz2]);
    
    first.value.first = add(first.value.first, second.value.first);
    first.value.second = add(first.value.second, second.value.second);

    first.sz += second.sz;

    first.lazy = -1;
    return first;
  }
  
  void build(int x, int lx, int rx, string& str) {
    tree[x].sz = rx - lx;

    if(rx - lx == 1) {
      if(lx < n) {
        tree[x].value = {str[lx] - 'a' + 1, str[lx] - 'a' + 1};
        tree[x].lazy = -1;
      }
    } else {
      int mid = (lx + rx) / 2;
      build(2 * x + 1, lx, mid, str);
      build(2 * x + 2, mid, rx, str);

      tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
  }

  void init(long long s, string& str) {
    while(size < s) {
      size *= 2;
    }
    tree.assign(2 * size - 1, {{0, 0}, 0, -1});
    build(0, 0, size, str);
  }
 
  void upd(int l, int r, long long value, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return;
    }
 
    if(lx >= l && rx <= r) {
      int sz = tree[x].sz;
      tree[x].value = {hi1[value][sz], hi2[value][sz]};
      tree[x].lazy = value;
      propagate(x, lx, rx);
      return;
    }
 
    int mid = (lx + rx) / 2;
    upd(l, r, value, 2 * x + 1, lx, mid);
    upd(l, r, value, 2 * x + 2, mid, rx);
    
    // dbg(tree[2 * x + 1].value)
    // dbg(tree[2 * x + 2].value)
    tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void upd(int l, int r, long long value) {
    upd(l, r, value, 0, 0, size);
  }
 
  node qry(int l, int r, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return {{0, 0}, 0, -1};
    }
 
    if(lx >= l && rx <= r) {
      return tree[x];
    }
 
    int mid = (lx + rx) / 2;
    node s1 = qry(l, r, 2 * x + 1, lx, mid);
    node s2 = qry(l, r, 2 * x + 2, mid, rx);
 
    return merge(s1, s2);
  }
 
  node qry(int l, int r) {
    return qry(l, r, 0, 0, size);
  }
};
segTree seg;

set<string> all;

long long compute1(int l, int r) {
  return (h1[l] - (pw1[r - l + 1] * h1[r + 1]) % mod + mod) % mod;
}
 
long long compute2(int l, int r) {
  return (h2[l] - (pw2[r - l + 1] * h2[r + 1]) % mod + mod) % mod;
}

string cross(string &a, string &b) {
  string res = "";
  for(int i = 0; i < n; i++) {
    if(a[i] == b[i]) {
      res += a[i];
    } else {
      set<char> st;
      
      st.insert('a');
      st.insert('b');
      st.insert('c');

      st.erase(a[i]);
      st.erase(b[i]);
      res += *st.begin();
    }
  }

  return res;
}



void solve_() {
  cin >> n;

  for(int i = 0; i < 3; i++) {
    cin >> s[i];
    for(int j = 0; j < n; j++) {
      if(s[i][j] == 'J') {
        s[i][j] = 'a';
      } else if(s[i][j] == 'O') {
        s[i][j] = 'b';
      } else {
        s[i][j] = 'c';
      }
    }
  }

  if(s[0] == s[1] && s[1] == s[2]) {
    for(int i = n - 1; i >= 0; i--) {
      h1[i] = ((h1[i + 1] * 53) % mod + s[0][i] - 'a' + 1) % mod; 
      h2[i] = ((h2[i + 1] * 31) % mod + s[0][i] - 'a' + 1) % mod; 
    }

    pair<long long, long long> need = {h1[0], h2[0]};
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i <= n; i++) {
      pw1[i] = (pw1[i - 1] * 53) % mod;
      pw2[i] = (pw2[i - 1] * 31) % mod; 
    }

    for(int i = 1; i <= 3; i++) {
      hi1[i][1] = i;
      hi2[i][1] = i;
      for(int j = 2; j <= n; j++) {
        hi1[i][j] = add(hi1[i][j - 1], mult(i, pw1[j - 1]));
        hi2[i][j] = add(hi2[i][j - 1], mult(i, pw2[j - 1]));
      }
    }

    int q; cin >> q;

    string k; cin >> k;

    for(int i = 0; i < n; i++) {
      if(k[i] == 'J') k[i] = 'a';
      if(k[i] == 'O') k[i] = 'b';
      if(k[i] == 'I') k[i] = 'c';
    }
    seg.init(n + 2, k);

    if(seg.tree[0].value == need) {
      cout << "Yes" << '\n';
    } else {
      cout << "No" << '\n';
    }

    // dbg(need)
    while(q--) {
      int l, r;
      char ch;
      cin >> l >> r >> ch;
      l--, r--;

      if(ch == 'J') {
        seg.upd(l, r + 1, 1);
      } else if(ch == 'O') {
        seg.upd(l, r + 1, 2);
      } else {
        seg.upd(l, r + 1, 3);
      }

      // dbg(seg.tree[0].value)
      if(seg.tree[0].value == need) {
        cout << "Yes" << '\n';
      } else {
        cout << "No" << '\n';
      }
    }
  }
}

int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

Main.cpp: In member function 'void segTree::propagate(int, int, int)':
Main.cpp:124:9: warning: unused variable 'mid' [-Wunused-variable]
  124 |     int mid = (lx + rx) / 2;
      |         ^~~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 900 KB Output is correct
2 Correct 77 ms 1004 KB Output is correct
3 Correct 77 ms 944 KB Output is correct
4 Correct 73 ms 988 KB Output is correct
5 Correct 69 ms 1340 KB Output is correct
6 Correct 64 ms 1340 KB Output is correct
7 Correct 67 ms 1288 KB Output is correct
8 Correct 74 ms 1332 KB Output is correct
9 Correct 71 ms 1384 KB Output is correct
10 Correct 66 ms 1320 KB Output is correct
11 Correct 69 ms 1284 KB Output is correct
12 Correct 70 ms 1384 KB Output is correct
13 Correct 80 ms 1300 KB Output is correct
14 Correct 75 ms 1264 KB Output is correct
15 Correct 83 ms 1324 KB Output is correct
16 Correct 66 ms 1432 KB Output is correct
17 Correct 67 ms 1384 KB Output is correct
18 Correct 76 ms 1352 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 900 KB Output is correct
2 Correct 77 ms 1004 KB Output is correct
3 Correct 77 ms 944 KB Output is correct
4 Correct 73 ms 988 KB Output is correct
5 Correct 69 ms 1340 KB Output is correct
6 Correct 64 ms 1340 KB Output is correct
7 Correct 67 ms 1288 KB Output is correct
8 Correct 74 ms 1332 KB Output is correct
9 Correct 71 ms 1384 KB Output is correct
10 Correct 66 ms 1320 KB Output is correct
11 Correct 69 ms 1284 KB Output is correct
12 Correct 70 ms 1384 KB Output is correct
13 Correct 80 ms 1300 KB Output is correct
14 Correct 75 ms 1264 KB Output is correct
15 Correct 83 ms 1324 KB Output is correct
16 Correct 66 ms 1432 KB Output is correct
17 Correct 67 ms 1384 KB Output is correct
18 Correct 76 ms 1352 KB Output is correct
19 Correct 306 ms 34296 KB Output is correct
20 Correct 261 ms 35932 KB Output is correct
21 Correct 171 ms 36332 KB Output is correct
22 Correct 184 ms 34688 KB Output is correct
23 Correct 111 ms 5244 KB Output is correct
24 Correct 108 ms 5096 KB Output is correct
25 Correct 210 ms 37472 KB Output is correct
26 Correct 185 ms 37432 KB Output is correct
27 Correct 196 ms 37408 KB Output is correct
28 Correct 215 ms 37588 KB Output is correct
29 Correct 184 ms 37132 KB Output is correct
30 Correct 118 ms 5196 KB Output is correct
31 Correct 198 ms 37420 KB Output is correct
32 Correct 180 ms 35984 KB Output is correct
33 Correct 110 ms 5068 KB Output is correct
34 Correct 191 ms 37388 KB Output is correct
35 Correct 148 ms 32908 KB Output is correct
36 Correct 107 ms 5092 KB Output is correct
37 Correct 132 ms 5220 KB Output is correct
38 Correct 222 ms 37492 KB Output is correct
39 Correct 130 ms 37404 KB Output is correct
40 Correct 188 ms 31528 KB Output is correct
41 Correct 275 ms 37612 KB Output is correct
42 Correct 99 ms 36960 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 900 KB Output is correct
2 Correct 77 ms 1004 KB Output is correct
3 Correct 77 ms 944 KB Output is correct
4 Correct 73 ms 988 KB Output is correct
5 Correct 69 ms 1340 KB Output is correct
6 Correct 64 ms 1340 KB Output is correct
7 Correct 67 ms 1288 KB Output is correct
8 Correct 74 ms 1332 KB Output is correct
9 Correct 71 ms 1384 KB Output is correct
10 Correct 66 ms 1320 KB Output is correct
11 Correct 69 ms 1284 KB Output is correct
12 Correct 70 ms 1384 KB Output is correct
13 Correct 80 ms 1300 KB Output is correct
14 Correct 75 ms 1264 KB Output is correct
15 Correct 83 ms 1324 KB Output is correct
16 Correct 66 ms 1432 KB Output is correct
17 Correct 67 ms 1384 KB Output is correct
18 Correct 76 ms 1352 KB Output is correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 900 KB Output is correct
2 Correct 77 ms 1004 KB Output is correct
3 Correct 77 ms 944 KB Output is correct
4 Correct 73 ms 988 KB Output is correct
5 Correct 69 ms 1340 KB Output is correct
6 Correct 64 ms 1340 KB Output is correct
7 Correct 67 ms 1288 KB Output is correct
8 Correct 74 ms 1332 KB Output is correct
9 Correct 71 ms 1384 KB Output is correct
10 Correct 66 ms 1320 KB Output is correct
11 Correct 69 ms 1284 KB Output is correct
12 Correct 70 ms 1384 KB Output is correct
13 Correct 80 ms 1300 KB Output is correct
14 Correct 75 ms 1264 KB Output is correct
15 Correct 83 ms 1324 KB Output is correct
16 Correct 66 ms 1432 KB Output is correct
17 Correct 67 ms 1384 KB Output is correct
18 Correct 76 ms 1352 KB Output is correct
19 Correct 306 ms 34296 KB Output is correct
20 Correct 261 ms 35932 KB Output is correct
21 Correct 171 ms 36332 KB Output is correct
22 Correct 184 ms 34688 KB Output is correct
23 Correct 111 ms 5244 KB Output is correct
24 Correct 108 ms 5096 KB Output is correct
25 Correct 210 ms 37472 KB Output is correct
26 Correct 185 ms 37432 KB Output is correct
27 Correct 196 ms 37408 KB Output is correct
28 Correct 215 ms 37588 KB Output is correct
29 Correct 184 ms 37132 KB Output is correct
30 Correct 118 ms 5196 KB Output is correct
31 Correct 198 ms 37420 KB Output is correct
32 Correct 180 ms 35984 KB Output is correct
33 Correct 110 ms 5068 KB Output is correct
34 Correct 191 ms 37388 KB Output is correct
35 Correct 148 ms 32908 KB Output is correct
36 Correct 107 ms 5092 KB Output is correct
37 Correct 132 ms 5220 KB Output is correct
38 Correct 222 ms 37492 KB Output is correct
39 Correct 130 ms 37404 KB Output is correct
40 Correct 188 ms 31528 KB Output is correct
41 Correct 275 ms 37612 KB Output is correct
42 Correct 99 ms 36960 KB Output is correct
43 Incorrect 0 ms 212 KB Output isn't correct
44 Halted 0 ms 0 KB -