oj.uz

Submission #503442

# Submission time Handle Problem Language Result Execution time Memory
503442 2022-01-08T01:25:20 Z DanerZein Crossing (JOI21_crossing) C++14
3 / 100
 732 ms 19592 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N=8e5+10;
const ll mod=1e9+9;
string sa,sb,sc,t;
vector<int> x;
int n;
ll tr[MAX_N],la[MAX_N],spot[MAX_N];
map<char,int> dic;
vector<ll> pot;

void init(int node,int a,int b){
  if(a==b){
    tr[node]=(x[a]*pot[a]);
    la[node]=-1;
    spot[node]=pot[a];
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr[node]=tr[le]+tr[ri]; tr[node]%=mod;
  spot[node]=spot[le]+spot[ri]; spot[node]%=mod;
  la[node]=-1;
}
void propagar(int node){
  if(la[node]==-1) return;
  int le=2*node+1,ri=2*node+2;
  la[ri]=la[le]=la[node];
  tr[node]=la[node]*spot[node]; tr[node]%=mod;
  la[node]=-1;
  return;
}
void update(int node,int a,int b,int l,int r,int val){
  propagar(node);
  if(a>r || b<l) return;
  if(l<=a && r>=b){
    la[node]=val;
    propagar(node);
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  update(le,a,mid,l,r,val);
  update(ri,mid+1,b,l,r,val);
  tr[node]=tr[le]+tr[ri]; tr[node]%=mod;
}

int main(){
  dic['J']=0;
  dic['O']=1;
  dic['I']=2;
  cin>>n;
  pot.push_back(1);
  for(int i=1;i<n;i++){
    pot.push_back(pot[i-1]*5);
    pot[i]%=mod;
  }
  cin>>sa>>sb>>sc;
  int q; cin>>q;
  cin>>t;
  ll so=0;
  for(int i=0;i<n;i++){
    so=(so+dic[sa[i]]*pot[i])%mod;
    x.push_back(dic[t[i]]);
  }
  init(0,0,n-1);
  /* for(int i=0;i<=4;i++) cout<<tr[i]<<" ";
  cout<<endl;*/
  if(sa==t) cout<<"Yes\n";
  else cout<<"No\n";
  for(int i=0;i<q;i++){
    int l,r;
    char ch;
    cin>>l>>r>>ch;
    l--; r--;
    update(0,0,n-1,l,r,dic[ch]);
    /*cout<<tr[0]<<endl;
    for(int j=0;j<=4;j++) cout<<tr[j]<<" ";
    cout<<endl;
    for(int j=0;j<=4;j++) cout<<la[j]<<" ";
    cout<<endl;*/
    if(tr[0]==so) cout<<"Yes\n";
    else cout<<"No\n";
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 852 KB Output is correct
2 Correct 405 ms 888 KB Output is correct
3 Correct 363 ms 792 KB Output is correct
4 Correct 400 ms 812 KB Output is correct
5 Correct 320 ms 860 KB Output is correct
6 Correct 320 ms 824 KB Output is correct
7 Correct 341 ms 876 KB Output is correct
8 Correct 358 ms 864 KB Output is correct
9 Correct 403 ms 948 KB Output is correct
10 Correct 358 ms 960 KB Output is correct
11 Correct 431 ms 904 KB Output is correct
12 Correct 408 ms 804 KB Output is correct
13 Correct 507 ms 804 KB Output is correct
14 Correct 491 ms 896 KB Output is correct
15 Correct 499 ms 892 KB Output is correct
16 Correct 519 ms 848 KB Output is correct
17 Correct 440 ms 884 KB Output is correct
18 Correct 418 ms 920 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 852 KB Output is correct
2 Correct 405 ms 888 KB Output is correct
3 Correct 363 ms 792 KB Output is correct
4 Correct 400 ms 812 KB Output is correct
5 Correct 320 ms 860 KB Output is correct
6 Correct 320 ms 824 KB Output is correct
7 Correct 341 ms 876 KB Output is correct
8 Correct 358 ms 864 KB Output is correct
9 Correct 403 ms 948 KB Output is correct
10 Correct 358 ms 960 KB Output is correct
11 Correct 431 ms 904 KB Output is correct
12 Correct 408 ms 804 KB Output is correct
13 Correct 507 ms 804 KB Output is correct
14 Correct 491 ms 896 KB Output is correct
15 Correct 499 ms 892 KB Output is correct
16 Correct 519 ms 848 KB Output is correct
17 Correct 440 ms 884 KB Output is correct
18 Correct 418 ms 920 KB Output is correct
19 Correct 732 ms 19592 KB Output is correct
20 Correct 690 ms 17908 KB Output is correct
21 Incorrect 589 ms 19396 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 852 KB Output is correct
2 Correct 405 ms 888 KB Output is correct
3 Correct 363 ms 792 KB Output is correct
4 Correct 400 ms 812 KB Output is correct
5 Correct 320 ms 860 KB Output is correct
6 Correct 320 ms 824 KB Output is correct
7 Correct 341 ms 876 KB Output is correct
8 Correct 358 ms 864 KB Output is correct
9 Correct 403 ms 948 KB Output is correct
10 Correct 358 ms 960 KB Output is correct
11 Correct 431 ms 904 KB Output is correct
12 Correct 408 ms 804 KB Output is correct
13 Correct 507 ms 804 KB Output is correct
14 Correct 491 ms 896 KB Output is correct
15 Correct 499 ms 892 KB Output is correct
16 Correct 519 ms 848 KB Output is correct
17 Correct 440 ms 884 KB Output is correct
18 Correct 418 ms 920 KB Output is correct
19 Correct 335 ms 844 KB Output is correct
20 Correct 382 ms 808 KB Output is correct
21 Incorrect 335 ms 876 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 852 KB Output is correct
2 Correct 405 ms 888 KB Output is correct
3 Correct 363 ms 792 KB Output is correct
4 Correct 400 ms 812 KB Output is correct
5 Correct 320 ms 860 KB Output is correct
6 Correct 320 ms 824 KB Output is correct
7 Correct 341 ms 876 KB Output is correct
8 Correct 358 ms 864 KB Output is correct
9 Correct 403 ms 948 KB Output is correct
10 Correct 358 ms 960 KB Output is correct
11 Correct 431 ms 904 KB Output is correct
12 Correct 408 ms 804 KB Output is correct
13 Correct 507 ms 804 KB Output is correct
14 Correct 491 ms 896 KB Output is correct
15 Correct 499 ms 892 KB Output is correct
16 Correct 519 ms 848 KB Output is correct
17 Correct 440 ms 884 KB Output is correct
18 Correct 418 ms 920 KB Output is correct
19 Correct 732 ms 19592 KB Output is correct
20 Correct 690 ms 17908 KB Output is correct
21 Incorrect 589 ms 19396 KB Output isn't correct
22 Halted 0 ms 0 KB -