oj.uz

답안 #513138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
513138 2022-01-17T02:36:51 Z czhang2718 Crossing (JOI21_crossing) C++17
0 / 100
 888 ms 2920 KB 
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;

const int N=200001;
const int no_op=-1;

int n, q;
string a, b, c, t;

struct segtree{
  int n;
  string s;
  vector<vi> cnt;
  vector<int> lazy;
  vector<int> good;

  void build(int x, int lx, int rx){
    if(rx-lx==1){
      cnt[x][s[lx]-'0']=1;
      return;
    }
    int m=(lx+rx)/2;
    build(2*x+1, lx, m);
    build(2*x+2, m, rx);
    for(int i=0; i<3; i++){
      cnt[x][i]=cnt[2*x+1][i]+cnt[2*x+2][i];
    }
  }

  segtree(int n, string s){
    this->n=n, this->s=s;
    cnt.resize(4*n, vi(3));
    lazy.resize(4*n, no_op);
    good.resize(4*n); 
    build(0, 0, n);
  }

  void push(int x, int lx, int rx){
    if(rx-lx==1 || lazy[x]==no_op) return;
    int v=lazy[x];
    good[2*x+1]=cnt[2*x+1][v];
    good[2*x+2]=cnt[2*x+2][v];
    lazy[2*x+1]=lazy[2*x+2]=v;
    lazy[x]=no_op;
  }

  void upd(int l, int r, int v, int x, int lx, int rx){
    push(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
      lazy[x]=v;
      good[x]=cnt[x][v];
      return;
    }
    int m=(lx+rx)/2;
    upd(l, r, v, 2*x+1, lx, m);
    upd(l, r, v, 2*x+2, m, rx);
    good[x]=good[2*x+1]+good[2*x+2];
  }

  void upd(int l, int r, int v){ upd(l, r, v, 0, 0, n); }
  bool query(){ return good[0]==n; }
};

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> a >> b >> c;
  map<char, char> mp={{'J', '0'}, {'O', '1'}, {'I', '2'}};
  for(int i=0; i<n; i++){
    a[i]=mp[a[i]];
    b[i]=mp[b[i]];
    c[i]=mp[c[i]];
  }

  vector<segtree> seg;
  // vector<string> vec;
  for(int i=-1; i<=1; i++){
    for(int j=-1; j<=1; j++){
      for(int k=-1; k<=1; k++){
        if(!i && !j && !k) continue;
        string s="";
        for(int p=0; p<n; p++){
          int A=a[p]-'0';
          int B=b[p]-'0';
          int C=c[p]-'0';
          int d=(i*A+j*B+k*C+9)%3;
          s+=static_cast<char>('0'+d);
        }
        // cout << s << "\n";
        // vec.push_back(s);
        segtree st(n, s);
        seg.push_back(st);
      }
    }
  }

  auto upd=[&](int l, int r, int v){
    for(int i=0; i<26; i++){
      seg[i].upd(l, r, v);
    }
  };

  auto any=[&]()->bool{
    for(int i=0; i<26; i++){
      // if(seg[i].query()){
      //   cout << vec[i] << " good\n";
      // }
      if(seg[i].query()) return 1;
    }
    return 0;
  };

  cin >> q;
  string t; cin >> t;
  for(int i=0; i<n; i++){
    upd(i, i+1, mp[t[i]]-'0');
  }
  cout << (any()?"Yes":"No") << "\n";
  while(q--){
    int l, r; char c; cin >> l >> r >> c;
    l--, r--;
    int v=mp[c]-'0';
    upd(l, r+1, v);
    cout << (any()?"Yes":"No") << "\n";
  }
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 888 ms 2920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 888 ms 2920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 888 ms 2920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 888 ms 2920 KB Output isn't correct
2 Halted 0 ms 0 KB -