| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 502297 |
2022-01-05T17:52:08 Z |
cig32 |
Crossing (JOI21_crossing) |
C++17 |
|
478 ms |
1048580 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng);
return u;
}
long long bm(long long b, long long p) { // bigmod
if(p==0) return 1;
long long r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
string gene(string a, string b) {
string c;
for(int i=0; i<a.size(); i++) {
if(a[i] == b[i]) c += a[i];
else {
string t = "JOI";
for(int j=0; j<3; j++) {
if(a[i] != t[j] && b[i] != t[j]) c += t[j];
}
}
}
return c;
}
struct segtree_rurq {
// Range update range query, standard form 4 (assignment/sum)
struct node {
long long upd = 0;
long long ans = 0;
bool exist = 0;
} a[4*MAXN];
long long mod = 0;
//To be remained unchanged
void u(int l, int r, int constl, int constr, int idx, long long val) {
if(l <= constl && constr <= r) {
a[idx].upd = val;
a[idx].ans = val * (constr-constl+1);
a[idx].exist = 1;
if(mod) {
a[idx].upd %= mod;
a[idx].ans %= mod;
}
return;
}
int mid = (constl+constr) >> 1;
//Lazy propagation
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
else {
u(l, r, constl, mid, 2*idx+1, val);
u(l, r, mid+1, constr, 2*idx+2, val);
}
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
if(mod) a[idx].ans %= mod;
}
long long qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return a[idx].ans;
int mid = (constl+constr) >> 1;
long long ret;
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) {
ret = qu(l, r, mid+1, constr, 2*idx+2);
}
else if(constr<l || r<mid+1) {
ret = qu(l, r, constl, mid, 2*idx+1);
}
else {
ret = qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
}
if(mod) ret %= mod;
return ret;
}
public:
void set_mod(long long x) {
mod = x;
}
void update(int l, int r, long long v) {
u(l, r, 0, MAXN-1, 0, v);
}
long long query(int l, int r) {
return qu(l, r, 0, MAXN-1, 0);
}
};
void solve(int tc) {
int N;
cin >> N;
string s[9];
for(int i=0; i<3; i++) cin >> s[i];
s[3] = gene(s[0], s[1]);
s[4] = gene(s[0], s[2]);
s[5] = gene(s[1], s[2]);
s[6] = gene(s[2], s[3]);
s[7] = gene(s[1], s[4]);
s[8] = gene(s[0], s[5]);
segtree_rurq st[9][3][3];
string word = "JOI";
unordered_map<char, int> code;
code['J']=0, code['O']=1, code['I']=2;
int dist[9] = {};
int Q;
cin >> Q;
string t0;
cin >> t0;
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
if(t0[j] != s[i][j]) dist[i]++;
}
}
vector<int> lis[9][3];
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
lis[i][code[s[i][j]]].push_back(j+1);
}
}
for(int i=0; i<9; i++) {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
if(lis[i][j].empty()) continue;
st[i][j][k].update(0, lis[i][j].size(), 0);
for(int l=0; l<lis[i][j].size(); l++) {
if(t0[lis[i][j][l] - 1] == word[k]) {
st[i][j][k].update(l+1, l+1, 1);
}
}
}
}
}
for(int i=0; i<=Q; i++) {
if(i > 0) {
int l, r;
cin >> l >> r;
char c;
cin >> c;
int L[9][3], R[9][3];
for(int j=0; j<9; j++) {
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) {
L[j][k] = R[j][k] = -1;
continue;
}
int lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb) >> 1;
if(lis[j][k][mid] >= l) rb = mid;
else lb = mid+1;
}
L[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb+1) >> 1;
if(lis[j][k][mid] <= r) lb = mid;
else rb = mid-1;
}
R[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
}
}
for(int j=0; j<9; j++) {
for(int k=0; k<3; k++) {
if(L[j][k] == -1 || R[j][k] == -1) continue;
for(int m=0; m<3; m++) {
st[j][k][m].update(L[j][k], R[j][k], 0);
}
st[j][k][code[c]].update(L[j][k], R[j][k], 1);
}
dist[j] = 0;
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) continue;
for(int m=0; m<3; m++) {
if(k != m) dist[j] += st[j][k][m].query(1, lis[j][k].size());
}
}
}
}
bool ret = 0;
for(int j=0; j<9; j++) {
ret |= (dist[j] == 0);
}
cout << (ret ? "Yes\n" : "No\n");
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) {
solve(i);
}
}
Compilation message
Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
Main.cpp: In function 'void solve(int)':
Main.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int l=0; l<lis[i][j].size(); l++) {
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
