| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 788160 |
2023-07-19T20:44:29 Z |
anton |
Crossing (JOI21_crossing) |
C++17 |
|
477 ms |
2732 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2*1e5;
struct Node{
bool ok;
int v;
Node(bool _ok, int _v){
ok = _ok;
v= _v;
}
Node(){
ok = true;
}
};
Node op(Node& a, Node& b){
if(a.ok && b.ok){
if(a.v == b.v){
return Node(true, a.v);
}
return Node(false, -1);
}
return Node(false, -1);
}
struct Tree{
int s, m;
map<int, int> small;
vector<Node> tree;
vector<Node> model;
vector<bool> ac;
vector<Node> d;
Tree(){};
Tree (vector<Node>& mo, vector<Node>& v, map<int, int> sm){
s = v.size();
m = 1;
while(m<s){
m*=2;
}
m*=2;
tree.resize(m);
d.resize(m);
model.resize(m);
ac.resize(m);
swap(small, sm);
build(v,mo, 0, s-1, 1);
}
void ap(int id){
tree[id] =d[id];
if(tree[id].ok && model[id].ok){
tree[id].v = (tree[id].v- model[id].v+3)%3;
}
else{
tree[id].ok = false;
}
}
void push(int t, int lt, int rt){
if(lt!=rt && ac[t]){
d[t*2] = d[t];
ac[t] = false;
ac[t*2] =true;
ac[t*2+1]=true;
d[t*2+1] = d[t];
ap(t*2);
ap(t*2+1);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
}
void build(vector<Node>&v, vector<Node>& mo, int lt, int rt, int t){
if(lt == rt){
model[t] = mo[lt];
d[t] = v[lt];
ap(t);
}
else{
int mid = (lt+rt)/2;
build(v,mo, lt, mid, t*2);
build(v,mo, mid+1, rt, t*2+1);
model[t]= op(model[t*2], model[t*2+1]);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
}
void update(int l, int r, Node v, int lt, int rt, int t){
if(l<=lt && rt<=r){
d[t] = v;
ac[t] = true;
ap(t);
}
else if(r<lt|| rt<l){
return;
}
else{
int mid = (lt+rt)/2;
push(t*2, lt, mid);
push(t*2+1, mid+1, rt);
update(l, r, v, lt, mid, t*2);
update(l, r, v, mid+1, rt, t*2+1);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
}
void request(int l, int r, int v){
auto l_it = small.lower_bound(l);
auto r_it = small.upper_bound(r);
if(r_it==small.begin()){
return;
}
--r_it;
if(l_it!=small.end() && r_it!=small.end() && l_it->second <= r_it -> second){
update(l_it->second, r_it->second, Node(true, v), 0, s-1, 1);
}
}
}forest[3][3];
int n, q, v[3][3], t[MAX_N][2];
bool is_set[3][3];
string s[3], r;
bool upd_val(int x, int y, int val){
if(!is_set[x][y]){
is_set[x][y] = true;
v[x][y] = val;
}
else{
if(v[x][y] != val){
return false;
}
}
return true;
}
signed main(){
cin>>n;
for(int i = 0; i<3; i++){
cin>>s[i];
}
map<char, int> m;
m['J'] = 0;
m['O'] = 1;
m['I'] = 2;
for(int i = 0; i<n; i++){
t[i][0] =(m[s[1][i]] -m[s[0][i]] +3)%3;
t[i][1] =(m[s[2][i]] - m[s[0][i]] + 3)%3;
}
fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);
cin>>q;
cin>>r;
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
vector<Node> v, mod;
map<int, int> small;
for(int i = 0; i<n; i++){
if(t[i][0] == x && t[i][1] == y){
v.push_back(Node(true, m[r[i]]));
mod.push_back(Node(true, m[s[0][i]]));
small.insert(pair<int, int>(i, small.size()));
}
}
if(v.size()>0){
forest[x][y] = Tree(mod, v, small);
}
}
}
bool ok = true;
is_set[0][0] = true;
v[0][0] =0;
for(int i = -1; i<q; i++){
ok = true;
fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);
is_set[0][0] = true;
if(i >=0){
int l, ri;
char c;
cin>>l>>ri>>c;
l--;
ri--;
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
if(forest[x][y].tree.size()>0){
forest[x][y].request(l, ri, m[c]);
}
}
}
}
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
if(forest[x][y].tree.size()>0){
is_set[x][y] = forest[x][y].tree[1].ok;
ok &= forest[x][y].tree[1].ok;
v[x][y] = forest[x][y].tree[1].v;
if(x==0 && y==0){
ok &= v[x][y]==0;
}
}
}
}
for(int i = 0; i<9; i++){
for(int b= 0; b<9; b++){
for(int e = 0; e<9; e++){
if(is_set[b/3][b%3] && is_set[e/3][e%3]){
ok &= upd_val((e/3 + b/3)%3, (e+b)%3, (v[e/3][e%3] + v[b/3][b%3])%3);
}
}
}
}
if(ok){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
2212 KB |
Output is correct |
| 2 |
Correct |
467 ms |
2732 KB |
Output is correct |
| 3 |
Correct |
477 ms |
2268 KB |
Output is correct |
| 4 |
Incorrect |
457 ms |
2388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
2212 KB |
Output is correct |
| 2 |
Correct |
467 ms |
2732 KB |
Output is correct |
| 3 |
Correct |
477 ms |
2268 KB |
Output is correct |
| 4 |
Incorrect |
457 ms |
2388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
2212 KB |
Output is correct |
| 2 |
Correct |
467 ms |
2732 KB |
Output is correct |
| 3 |
Correct |
477 ms |
2268 KB |
Output is correct |
| 4 |
Incorrect |
457 ms |
2388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
2212 KB |
Output is correct |
| 2 |
Correct |
467 ms |
2732 KB |
Output is correct |
| 3 |
Correct |
477 ms |
2268 KB |
Output is correct |
| 4 |
Incorrect |
457 ms |
2388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
