oj.uz

Submission #513179

# Submission time Handle Problem Language Result Execution time Memory
513179 2022-01-17T03:17:02 Z czhang2718 Crossing (JOI21_crossing) C++17
100 / 100
 2640 ms 355480 KB 
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;

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

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

struct segtree{
  int n;
  string s;
  int cnt[N][3];
  int good[N];
  int lazy[N];

  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;
    for(int i=0; i<4*n; i++){
      cnt[i][0]=cnt[i][1]=cnt[i][2]=0;
      good[i]=0;
      lazy[i]=no_op;
    }
    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<int> h(3);
  h[0]=h[1]=h[2]=1;
  for(int z=0; z<3; z++){
    h[z]=-1;
    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=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=1;
  }

  h[0]=h[1]=h[2]=-1;
  for(int z=0; z<3; z++){
    h[z]=0;
    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=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=-1;
  }

  h[0]=h[1]=h[2]=0;
  for(int z=0; z<3; z++){
    h[z]=1;
    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=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=0;
  }

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

  auto any=[&]()->bool{
    for(int i=0; i<9; i++){
      if(seg[i].query()) return 1;
    }
    return 0;
  };

  cin >> q >> 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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 352456 KB Output is correct
2 Correct 390 ms 352448 KB Output is correct
3 Correct 390 ms 352528 KB Output is correct
4 Correct 362 ms 352636 KB Output is correct
5 Correct 334 ms 352580 KB Output is correct
6 Correct 344 ms 352516 KB Output is correct
7 Correct 327 ms 352500 KB Output is correct
8 Correct 362 ms 352548 KB Output is correct
9 Correct 360 ms 352540 KB Output is correct
10 Correct 370 ms 352556 KB Output is correct
11 Correct 364 ms 352488 KB Output is correct
12 Correct 347 ms 352456 KB Output is correct
13 Correct 354 ms 352440 KB Output is correct
14 Correct 345 ms 352508 KB Output is correct
15 Correct 367 ms 352548 KB Output is correct
16 Correct 347 ms 352464 KB Output is correct
17 Correct 353 ms 352456 KB Output is correct
18 Correct 348 ms 352460 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 352456 KB Output is correct
2 Correct 390 ms 352448 KB Output is correct
3 Correct 390 ms 352528 KB Output is correct
4 Correct 362 ms 352636 KB Output is correct
5 Correct 334 ms 352580 KB Output is correct
6 Correct 344 ms 352516 KB Output is correct
7 Correct 327 ms 352500 KB Output is correct
8 Correct 362 ms 352548 KB Output is correct
9 Correct 360 ms 352540 KB Output is correct
10 Correct 370 ms 352556 KB Output is correct
11 Correct 364 ms 352488 KB Output is correct
12 Correct 347 ms 352456 KB Output is correct
13 Correct 354 ms 352440 KB Output is correct
14 Correct 345 ms 352508 KB Output is correct
15 Correct 367 ms 352548 KB Output is correct
16 Correct 347 ms 352464 KB Output is correct
17 Correct 353 ms 352456 KB Output is correct
18 Correct 348 ms 352460 KB Output is correct
19 Correct 2299 ms 355316 KB Output is correct
20 Correct 1879 ms 355332 KB Output is correct
21 Correct 1401 ms 355160 KB Output is correct
22 Correct 1419 ms 355156 KB Output is correct
23 Correct 575 ms 352700 KB Output is correct
24 Correct 618 ms 352676 KB Output is correct
25 Correct 1500 ms 355480 KB Output is correct
26 Correct 1555 ms 355296 KB Output is correct
27 Correct 1878 ms 355332 KB Output is correct
28 Correct 1940 ms 355340 KB Output is correct
29 Correct 1986 ms 355316 KB Output is correct
30 Correct 868 ms 352716 KB Output is correct
31 Correct 1962 ms 355392 KB Output is correct
32 Correct 1777 ms 355120 KB Output is correct
33 Correct 661 ms 352672 KB Output is correct
34 Correct 1892 ms 355380 KB Output is correct
35 Correct 1253 ms 354788 KB Output is correct
36 Correct 581 ms 352712 KB Output is correct
37 Correct 562 ms 352672 KB Output is correct
38 Correct 1629 ms 355324 KB Output is correct
39 Correct 811 ms 355296 KB Output is correct
40 Correct 1213 ms 354488 KB Output is correct
41 Correct 2640 ms 355320 KB Output is correct
42 Correct 531 ms 355344 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 352456 KB Output is correct
2 Correct 390 ms 352448 KB Output is correct
3 Correct 390 ms 352528 KB Output is correct
4 Correct 362 ms 352636 KB Output is correct
5 Correct 334 ms 352580 KB Output is correct
6 Correct 344 ms 352516 KB Output is correct
7 Correct 327 ms 352500 KB Output is correct
8 Correct 362 ms 352548 KB Output is correct
9 Correct 360 ms 352540 KB Output is correct
10 Correct 370 ms 352556 KB Output is correct
11 Correct 364 ms 352488 KB Output is correct
12 Correct 347 ms 352456 KB Output is correct
13 Correct 354 ms 352440 KB Output is correct
14 Correct 345 ms 352508 KB Output is correct
15 Correct 367 ms 352548 KB Output is correct
16 Correct 347 ms 352464 KB Output is correct
17 Correct 353 ms 352456 KB Output is correct
18 Correct 348 ms 352460 KB Output is correct
19 Correct 397 ms 352516 KB Output is correct
20 Correct 393 ms 352588 KB Output is correct
21 Correct 351 ms 352508 KB Output is correct
22 Correct 335 ms 352584 KB Output is correct
23 Correct 344 ms 352468 KB Output is correct
24 Correct 349 ms 352552 KB Output is correct
25 Correct 350 ms 352568 KB Output is correct
26 Correct 336 ms 352528 KB Output is correct
27 Correct 345 ms 352456 KB Output is correct
28 Correct 340 ms 352444 KB Output is correct
29 Correct 347 ms 352452 KB Output is correct
30 Correct 318 ms 352472 KB Output is correct
31 Correct 348 ms 352516 KB Output is correct
32 Correct 340 ms 352548 KB Output is correct
33 Correct 353 ms 352484 KB Output is correct
34 Correct 340 ms 352444 KB Output is correct
35 Correct 361 ms 352584 KB Output is correct
36 Correct 346 ms 352464 KB Output is correct
37 Correct 357 ms 352656 KB Output is correct
38 Correct 349 ms 352428 KB Output is correct
39 Correct 354 ms 352528 KB Output is correct
40 Correct 349 ms 352540 KB Output is correct
41 Correct 352 ms 352680 KB Output is correct
42 Correct 350 ms 352440 KB Output is correct
43 Correct 342 ms 352508 KB Output is correct
44 Correct 349 ms 352500 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 352456 KB Output is correct
2 Correct 390 ms 352448 KB Output is correct
3 Correct 390 ms 352528 KB Output is correct
4 Correct 362 ms 352636 KB Output is correct
5 Correct 334 ms 352580 KB Output is correct
6 Correct 344 ms 352516 KB Output is correct
7 Correct 327 ms 352500 KB Output is correct
8 Correct 362 ms 352548 KB Output is correct
9 Correct 360 ms 352540 KB Output is correct
10 Correct 370 ms 352556 KB Output is correct
11 Correct 364 ms 352488 KB Output is correct
12 Correct 347 ms 352456 KB Output is correct
13 Correct 354 ms 352440 KB Output is correct
14 Correct 345 ms 352508 KB Output is correct
15 Correct 367 ms 352548 KB Output is correct
16 Correct 347 ms 352464 KB Output is correct
17 Correct 353 ms 352456 KB Output is correct
18 Correct 348 ms 352460 KB Output is correct
19 Correct 2299 ms 355316 KB Output is correct
20 Correct 1879 ms 355332 KB Output is correct
21 Correct 1401 ms 355160 KB Output is correct
22 Correct 1419 ms 355156 KB Output is correct
23 Correct 575 ms 352700 KB Output is correct
24 Correct 618 ms 352676 KB Output is correct
25 Correct 1500 ms 355480 KB Output is correct
26 Correct 1555 ms 355296 KB Output is correct
27 Correct 1878 ms 355332 KB Output is correct
28 Correct 1940 ms 355340 KB Output is correct
29 Correct 1986 ms 355316 KB Output is correct
30 Correct 868 ms 352716 KB Output is correct
31 Correct 1962 ms 355392 KB Output is correct
32 Correct 1777 ms 355120 KB Output is correct
33 Correct 661 ms 352672 KB Output is correct
34 Correct 1892 ms 355380 KB Output is correct
35 Correct 1253 ms 354788 KB Output is correct
36 Correct 581 ms 352712 KB Output is correct
37 Correct 562 ms 352672 KB Output is correct
38 Correct 1629 ms 355324 KB Output is correct
39 Correct 811 ms 355296 KB Output is correct
40 Correct 1213 ms 354488 KB Output is correct
41 Correct 2640 ms 355320 KB Output is correct
42 Correct 531 ms 355344 KB Output is correct
43 Correct 397 ms 352516 KB Output is correct
44 Correct 393 ms 352588 KB Output is correct
45 Correct 351 ms 352508 KB Output is correct
46 Correct 335 ms 352584 KB Output is correct
47 Correct 344 ms 352468 KB Output is correct
48 Correct 349 ms 352552 KB Output is correct
49 Correct 350 ms 352568 KB Output is correct
50 Correct 336 ms 352528 KB Output is correct
51 Correct 345 ms 352456 KB Output is correct
52 Correct 340 ms 352444 KB Output is correct
53 Correct 347 ms 352452 KB Output is correct
54 Correct 318 ms 352472 KB Output is correct
55 Correct 348 ms 352516 KB Output is correct
56 Correct 340 ms 352548 KB Output is correct
57 Correct 353 ms 352484 KB Output is correct
58 Correct 340 ms 352444 KB Output is correct
59 Correct 361 ms 352584 KB Output is correct
60 Correct 346 ms 352464 KB Output is correct
61 Correct 357 ms 352656 KB Output is correct
62 Correct 349 ms 352428 KB Output is correct
63 Correct 354 ms 352528 KB Output is correct
64 Correct 349 ms 352540 KB Output is correct
65 Correct 352 ms 352680 KB Output is correct
66 Correct 350 ms 352440 KB Output is correct
67 Correct 342 ms 352508 KB Output is correct
68 Correct 349 ms 352500 KB Output is correct
69 Correct 2044 ms 355152 KB Output is correct
70 Correct 1924 ms 355288 KB Output is correct
71 Correct 590 ms 352648 KB Output is correct
72 Correct 636 ms 352608 KB Output is correct
73 Correct 631 ms 352672 KB Output is correct
74 Correct 1339 ms 354968 KB Output is correct
75 Correct 584 ms 352644 KB Output is correct
76 Correct 1460 ms 355336 KB Output is correct
77 Correct 1471 ms 354936 KB Output is correct
78 Correct 586 ms 352680 KB Output is correct
79 Correct 584 ms 352652 KB Output is correct
80 Correct 1310 ms 354680 KB Output is correct
81 Correct 583 ms 352672 KB Output is correct
82 Correct 1440 ms 355352 KB Output is correct
83 Correct 1504 ms 355348 KB Output is correct
84 Correct 594 ms 352688 KB Output is correct
85 Correct 559 ms 352608 KB Output is correct
86 Correct 1732 ms 354736 KB Output is correct
87 Correct 1874 ms 355380 KB Output is correct
88 Correct 663 ms 353068 KB Output is correct
89 Correct 1763 ms 355008 KB Output is correct
90 Correct 1907 ms 355352 KB Output is correct
91 Correct 670 ms 352660 KB Output is correct
92 Correct 1399 ms 354800 KB Output is correct
93 Correct 595 ms 352828 KB Output is correct
94 Correct 596 ms 352656 KB Output is correct
95 Correct 567 ms 352676 KB Output is correct
96 Correct 1627 ms 355292 KB Output is correct
97 Correct 809 ms 355344 KB Output is correct
98 Correct 1230 ms 354520 KB Output is correct
99 Correct 2588 ms 355340 KB Output is correct
100 Correct 527 ms 355400 KB Output is correct