oj.uz

Submission #704958

# Submission time Handle Problem Language Result Execution time Memory
704958 2023-03-03T07:19:13 Z MtSaka Crossing (JOI21_crossing) C++17
100 / 100
 4014 ms 106928 KB 
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
using ll=long long;
using namespace std;
using ull=unsigned long long;
int get_id(char c){
  if(c=='J')return 0;
  if(c=='O')return 1;
  return 2;
}
char from_id(int a){
  if(a==0)return 'J';
  if(a==1)return 'O';
  return 'I';
}
vector<string>v;
vector sum(3,vector(9,vector<ll>()));
struct segment_tree{
  private:
  int n,id,sz,lg;
  vector<ll>seg;
  vector<int>lazy;
  void eval(int k,int l,int r){
    if(lazy[k]!=-1){
      seg[k]=sum[lazy[k]][id][min(n,r)]-sum[lazy[k]][id][l];
      if(r-l>1)lazy[k<<1]=lazy[k],lazy[k<<1|1]=lazy[k];
    }
    lazy[k]=-1;
  }
  void update(int i){
    seg[i]=seg[i<<1]+seg[i<<1|1];
  }
  public:
  segment_tree()=default;
  segment_tree(string s,int id):n(s.size()),id(id){
    sz=1,lg=0;
    while(sz<n)sz<<=1,lg++;
    seg.resize(sz<<1);
    rep(i,0,n){
      seg[i+sz]=(s[i]!=v[id][i]);
    }
    rrep(i,1,sz)update(i);
    lazy.assign(sz<<1,-1);
  }
  void apply(int l,int r,int a,int id=1,int l1=0,int r1=-1){
    if(r1<0)r1=sz;
    eval(id,l1,r1);
    if(r<=l1||r1<=l)return;
    if(l<=l1&&r1<=r){
      lazy[id]=a;
      eval(id,l1,r1);
    }
    else{
      apply(l,r,a,id<<1,l1,(l1+r1)>>1);
      apply(l,r,a,id<<1|1,(l1+r1)>>1,r1);
      update(id);
    }
  }
  int prod(int l,int r,int id=1,int l1=0,int r1=-1){
    if(r1<0)r1=sz;
    if(r1<=l||r<=l1)return 0;
    eval(id,l1,r1);
    if(l<=l1&&r1<=r)return seg[id];
    return prod(l,r,id<<1,l1,(l1+r1)>>1)+prod(l,r,id<<1|1,(l1+r1)>>1,r1);
  }
};
string f(string a,string b){
  assert(a.size()==b.size());
  string ans(a.size(),'1');
  rep(i,0,a.size()){
    if(get_id(a[i])==get_id(b[i]))ans[i]=a[i];
    else ans[i]=from_id(3^get_id(a[i])^get_id(b[i]));
  }
  return ans;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;cin>>n;
  string a,b,c;cin>>a>>b>>c;
  v.emplace_back(a);
  v.emplace_back(b);
  v.emplace_back(c);
  //cerr<<a<<" "<<b<<" "<<c<<endl;
  string ab=f(a,b),bc=f(b,c),ac=f(a,c),abbc=f(ab,bc),abac=f(ab,ac),bcac=f(bc,ac);
  v.emplace_back(ab);
  v.emplace_back(bc);
  v.emplace_back(ac);
  v.emplace_back(abbc);
  v.emplace_back(abac);
  v.emplace_back(bcac);
  rep(i,0,9){
    rep(j,0,3)sum[j][i].resize(n+1);
    rep(j,0,n){
      rep(k,0,3)if(get_id(v[i][j])!=k)sum[k][i][j+1]=1;
    }
    rep(j,0,n){
      sum[0][i][j+1]+=sum[0][i][j];
      sum[1][i][j+1]+=sum[1][i][j];
      sum[2][i][j+1]+=sum[2][i][j];
    }
  }
  int q;cin>>q;
  string t;cin>>t;
  vector<segment_tree>seg(9);
  auto calc=[&]()->bool {
    rep(i,0,9)if(seg[i].prod(0,n)==0)return true;
    return false;
  };
  rep(i,0,9)seg[i]=segment_tree(t,i);
  if(calc()){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
  rep(i,0,q){
    int l,r;char c;
    cin>>l>>r>>c;
    l--;
    rep(j,0,9)seg[j].apply(l,r,get_id(c));
    //cerr<<seg.all_prod()<<endl;
    if(calc()){
      cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1000 KB Output is correct
2 Correct 646 ms 876 KB Output is correct
3 Correct 673 ms 920 KB Output is correct
4 Correct 578 ms 988 KB Output is correct
5 Correct 551 ms 1024 KB Output is correct
6 Correct 489 ms 868 KB Output is correct
7 Correct 571 ms 984 KB Output is correct
8 Correct 555 ms 908 KB Output is correct
9 Correct 546 ms 940 KB Output is correct
10 Correct 537 ms 868 KB Output is correct
11 Correct 574 ms 972 KB Output is correct
12 Correct 580 ms 1004 KB Output is correct
13 Correct 557 ms 920 KB Output is correct
14 Correct 549 ms 844 KB Output is correct
15 Correct 552 ms 884 KB Output is correct
16 Correct 556 ms 976 KB Output is correct
17 Correct 563 ms 936 KB Output is correct
18 Correct 608 ms 936 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1000 KB Output is correct
2 Correct 646 ms 876 KB Output is correct
3 Correct 673 ms 920 KB Output is correct
4 Correct 578 ms 988 KB Output is correct
5 Correct 551 ms 1024 KB Output is correct
6 Correct 489 ms 868 KB Output is correct
7 Correct 571 ms 984 KB Output is correct
8 Correct 555 ms 908 KB Output is correct
9 Correct 546 ms 940 KB Output is correct
10 Correct 537 ms 868 KB Output is correct
11 Correct 574 ms 972 KB Output is correct
12 Correct 580 ms 1004 KB Output is correct
13 Correct 557 ms 920 KB Output is correct
14 Correct 549 ms 844 KB Output is correct
15 Correct 552 ms 884 KB Output is correct
16 Correct 556 ms 976 KB Output is correct
17 Correct 563 ms 936 KB Output is correct
18 Correct 608 ms 936 KB Output is correct
19 Correct 4014 ms 103260 KB Output is correct
20 Correct 3388 ms 106332 KB Output is correct
21 Correct 2271 ms 103500 KB Output is correct
22 Correct 2012 ms 98928 KB Output is correct
23 Correct 1204 ms 9252 KB Output is correct
24 Correct 1057 ms 9248 KB Output is correct
25 Correct 2037 ms 106616 KB Output is correct
26 Correct 2085 ms 106636 KB Output is correct
27 Correct 2794 ms 106476 KB Output is correct
28 Correct 2602 ms 106672 KB Output is correct
29 Correct 2772 ms 105048 KB Output is correct
30 Correct 1363 ms 9160 KB Output is correct
31 Correct 2512 ms 106492 KB Output is correct
32 Correct 2560 ms 102272 KB Output is correct
33 Correct 1028 ms 9100 KB Output is correct
34 Correct 2561 ms 106472 KB Output is correct
35 Correct 1849 ms 94156 KB Output is correct
36 Correct 990 ms 9364 KB Output is correct
37 Correct 986 ms 9308 KB Output is correct
38 Correct 2774 ms 106480 KB Output is correct
39 Correct 976 ms 106608 KB Output is correct
40 Correct 1662 ms 62488 KB Output is correct
41 Correct 3575 ms 106928 KB Output is correct
42 Correct 750 ms 105856 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1000 KB Output is correct
2 Correct 646 ms 876 KB Output is correct
3 Correct 673 ms 920 KB Output is correct
4 Correct 578 ms 988 KB Output is correct
5 Correct 551 ms 1024 KB Output is correct
6 Correct 489 ms 868 KB Output is correct
7 Correct 571 ms 984 KB Output is correct
8 Correct 555 ms 908 KB Output is correct
9 Correct 546 ms 940 KB Output is correct
10 Correct 537 ms 868 KB Output is correct
11 Correct 574 ms 972 KB Output is correct
12 Correct 580 ms 1004 KB Output is correct
13 Correct 557 ms 920 KB Output is correct
14 Correct 549 ms 844 KB Output is correct
15 Correct 552 ms 884 KB Output is correct
16 Correct 556 ms 976 KB Output is correct
17 Correct 563 ms 936 KB Output is correct
18 Correct 608 ms 936 KB Output is correct
19 Correct 593 ms 1372 KB Output is correct
20 Correct 702 ms 1356 KB Output is correct
21 Correct 587 ms 1340 KB Output is correct
22 Correct 701 ms 1280 KB Output is correct
23 Correct 647 ms 1488 KB Output is correct
24 Correct 612 ms 1312 KB Output is correct
25 Correct 664 ms 1324 KB Output is correct
26 Correct 590 ms 1340 KB Output is correct
27 Correct 597 ms 1308 KB Output is correct
28 Correct 568 ms 1364 KB Output is correct
29 Correct 596 ms 1372 KB Output is correct
30 Correct 575 ms 1356 KB Output is correct
31 Correct 594 ms 1464 KB Output is correct
32 Correct 609 ms 1392 KB Output is correct
33 Correct 645 ms 1368 KB Output is correct
34 Correct 584 ms 1432 KB Output is correct
35 Correct 629 ms 1396 KB Output is correct
36 Correct 642 ms 1400 KB Output is correct
37 Correct 654 ms 1384 KB Output is correct
38 Correct 646 ms 1492 KB Output is correct
39 Correct 637 ms 1388 KB Output is correct
40 Correct 598 ms 1416 KB Output is correct
41 Correct 577 ms 1352 KB Output is correct
42 Correct 589 ms 1332 KB Output is correct
43 Correct 613 ms 1452 KB Output is correct
44 Correct 557 ms 1320 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1000 KB Output is correct
2 Correct 646 ms 876 KB Output is correct
3 Correct 673 ms 920 KB Output is correct
4 Correct 578 ms 988 KB Output is correct
5 Correct 551 ms 1024 KB Output is correct
6 Correct 489 ms 868 KB Output is correct
7 Correct 571 ms 984 KB Output is correct
8 Correct 555 ms 908 KB Output is correct
9 Correct 546 ms 940 KB Output is correct
10 Correct 537 ms 868 KB Output is correct
11 Correct 574 ms 972 KB Output is correct
12 Correct 580 ms 1004 KB Output is correct
13 Correct 557 ms 920 KB Output is correct
14 Correct 549 ms 844 KB Output is correct
15 Correct 552 ms 884 KB Output is correct
16 Correct 556 ms 976 KB Output is correct
17 Correct 563 ms 936 KB Output is correct
18 Correct 608 ms 936 KB Output is correct
19 Correct 4014 ms 103260 KB Output is correct
20 Correct 3388 ms 106332 KB Output is correct
21 Correct 2271 ms 103500 KB Output is correct
22 Correct 2012 ms 98928 KB Output is correct
23 Correct 1204 ms 9252 KB Output is correct
24 Correct 1057 ms 9248 KB Output is correct
25 Correct 2037 ms 106616 KB Output is correct
26 Correct 2085 ms 106636 KB Output is correct
27 Correct 2794 ms 106476 KB Output is correct
28 Correct 2602 ms 106672 KB Output is correct
29 Correct 2772 ms 105048 KB Output is correct
30 Correct 1363 ms 9160 KB Output is correct
31 Correct 2512 ms 106492 KB Output is correct
32 Correct 2560 ms 102272 KB Output is correct
33 Correct 1028 ms 9100 KB Output is correct
34 Correct 2561 ms 106472 KB Output is correct
35 Correct 1849 ms 94156 KB Output is correct
36 Correct 990 ms 9364 KB Output is correct
37 Correct 986 ms 9308 KB Output is correct
38 Correct 2774 ms 106480 KB Output is correct
39 Correct 976 ms 106608 KB Output is correct
40 Correct 1662 ms 62488 KB Output is correct
41 Correct 3575 ms 106928 KB Output is correct
42 Correct 750 ms 105856 KB Output is correct
43 Correct 593 ms 1372 KB Output is correct
44 Correct 702 ms 1356 KB Output is correct
45 Correct 587 ms 1340 KB Output is correct
46 Correct 701 ms 1280 KB Output is correct
47 Correct 647 ms 1488 KB Output is correct
48 Correct 612 ms 1312 KB Output is correct
49 Correct 664 ms 1324 KB Output is correct
50 Correct 590 ms 1340 KB Output is correct
51 Correct 597 ms 1308 KB Output is correct
52 Correct 568 ms 1364 KB Output is correct
53 Correct 596 ms 1372 KB Output is correct
54 Correct 575 ms 1356 KB Output is correct
55 Correct 594 ms 1464 KB Output is correct
56 Correct 609 ms 1392 KB Output is correct
57 Correct 645 ms 1368 KB Output is correct
58 Correct 584 ms 1432 KB Output is correct
59 Correct 629 ms 1396 KB Output is correct
60 Correct 642 ms 1400 KB Output is correct
61 Correct 654 ms 1384 KB Output is correct
62 Correct 646 ms 1492 KB Output is correct
63 Correct 637 ms 1388 KB Output is correct
64 Correct 598 ms 1416 KB Output is correct
65 Correct 577 ms 1352 KB Output is correct
66 Correct 589 ms 1332 KB Output is correct
67 Correct 613 ms 1452 KB Output is correct
68 Correct 557 ms 1320 KB Output is correct
69 Correct 3367 ms 98488 KB Output is correct
70 Correct 3507 ms 106336 KB Output is correct
71 Correct 1201 ms 9156 KB Output is correct
72 Correct 1031 ms 9312 KB Output is correct
73 Correct 1087 ms 9192 KB Output is correct
74 Correct 1989 ms 98376 KB Output is correct
75 Correct 1435 ms 9112 KB Output is correct
76 Correct 2441 ms 106448 KB Output is correct
77 Correct 2472 ms 98472 KB Output is correct
78 Correct 1304 ms 9152 KB Output is correct
79 Correct 1358 ms 9184 KB Output is correct
80 Correct 2257 ms 92412 KB Output is correct
81 Correct 1250 ms 9024 KB Output is correct
82 Correct 2346 ms 106508 KB Output is correct
83 Correct 2397 ms 103564 KB Output is correct
84 Correct 1407 ms 9052 KB Output is correct
85 Correct 1261 ms 9104 KB Output is correct
86 Correct 3158 ms 94812 KB Output is correct
87 Correct 3036 ms 106480 KB Output is correct
88 Correct 1997 ms 9156 KB Output is correct
89 Correct 2827 ms 100700 KB Output is correct
90 Correct 2627 ms 106464 KB Output is correct
91 Correct 1329 ms 9036 KB Output is correct
92 Correct 2071 ms 94384 KB Output is correct
93 Correct 1180 ms 9088 KB Output is correct
94 Correct 1267 ms 9068 KB Output is correct
95 Correct 1205 ms 9148 KB Output is correct
96 Correct 3344 ms 106284 KB Output is correct
97 Correct 1121 ms 106428 KB Output is correct
98 Correct 1878 ms 62428 KB Output is correct
99 Correct 3949 ms 106760 KB Output is correct
100 Correct 812 ms 105852 KB Output is correct