oj.uz

Submission #503441

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

const int MAX_N=8e5+10;
const int 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(tr[0]==so) 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 315 ms 960 KB Output is correct
2 Correct 352 ms 912 KB Output is correct
3 Correct 375 ms 896 KB Output is correct
4 Correct 328 ms 836 KB Output is correct
5 Correct 332 ms 872 KB Output is correct
6 Correct 325 ms 832 KB Output is correct
7 Correct 356 ms 920 KB Output is correct
8 Correct 339 ms 904 KB Output is correct
9 Correct 354 ms 888 KB Output is correct
10 Correct 342 ms 956 KB Output is correct
11 Correct 339 ms 904 KB Output is correct
12 Correct 345 ms 1104 KB Output is correct
13 Correct 339 ms 952 KB Output is correct
14 Correct 368 ms 888 KB Output is correct
15 Correct 348 ms 864 KB Output is correct
16 Correct 349 ms 912 KB Output is correct
17 Correct 351 ms 892 KB Output is correct
18 Correct 371 ms 884 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 960 KB Output is correct
2 Correct 352 ms 912 KB Output is correct
3 Correct 375 ms 896 KB Output is correct
4 Correct 328 ms 836 KB Output is correct
5 Correct 332 ms 872 KB Output is correct
6 Correct 325 ms 832 KB Output is correct
7 Correct 356 ms 920 KB Output is correct
8 Correct 339 ms 904 KB Output is correct
9 Correct 354 ms 888 KB Output is correct
10 Correct 342 ms 956 KB Output is correct
11 Correct 339 ms 904 KB Output is correct
12 Correct 345 ms 1104 KB Output is correct
13 Correct 339 ms 952 KB Output is correct
14 Correct 368 ms 888 KB Output is correct
15 Correct 348 ms 864 KB Output is correct
16 Correct 349 ms 912 KB Output is correct
17 Correct 351 ms 892 KB Output is correct
18 Correct 371 ms 884 KB Output is correct
19 Correct 609 ms 22104 KB Output is correct
20 Correct 525 ms 20064 KB Output is correct
21 Incorrect 528 ms 21528 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 960 KB Output is correct
2 Correct 352 ms 912 KB Output is correct
3 Correct 375 ms 896 KB Output is correct
4 Correct 328 ms 836 KB Output is correct
5 Correct 332 ms 872 KB Output is correct
6 Correct 325 ms 832 KB Output is correct
7 Correct 356 ms 920 KB Output is correct
8 Correct 339 ms 904 KB Output is correct
9 Correct 354 ms 888 KB Output is correct
10 Correct 342 ms 956 KB Output is correct
11 Correct 339 ms 904 KB Output is correct
12 Correct 345 ms 1104 KB Output is correct
13 Correct 339 ms 952 KB Output is correct
14 Correct 368 ms 888 KB Output is correct
15 Correct 348 ms 864 KB Output is correct
16 Correct 349 ms 912 KB Output is correct
17 Correct 351 ms 892 KB Output is correct
18 Correct 371 ms 884 KB Output is correct
19 Correct 334 ms 920 KB Output is correct
20 Correct 350 ms 900 KB Output is correct
21 Incorrect 355 ms 1048 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 960 KB Output is correct
2 Correct 352 ms 912 KB Output is correct
3 Correct 375 ms 896 KB Output is correct
4 Correct 328 ms 836 KB Output is correct
5 Correct 332 ms 872 KB Output is correct
6 Correct 325 ms 832 KB Output is correct
7 Correct 356 ms 920 KB Output is correct
8 Correct 339 ms 904 KB Output is correct
9 Correct 354 ms 888 KB Output is correct
10 Correct 342 ms 956 KB Output is correct
11 Correct 339 ms 904 KB Output is correct
12 Correct 345 ms 1104 KB Output is correct
13 Correct 339 ms 952 KB Output is correct
14 Correct 368 ms 888 KB Output is correct
15 Correct 348 ms 864 KB Output is correct
16 Correct 349 ms 912 KB Output is correct
17 Correct 351 ms 892 KB Output is correct
18 Correct 371 ms 884 KB Output is correct
19 Correct 609 ms 22104 KB Output is correct
20 Correct 525 ms 20064 KB Output is correct
21 Incorrect 528 ms 21528 KB Output isn't correct
22 Halted 0 ms 0 KB -