oj.uz

Submission #503444

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

const int MAX_N=8e5+10;
const unsigned long long mod=((ll)1<<(ll)60);
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(){
  //cout<<mod<<endl;
  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 307 ms 744 KB Output is correct
2 Correct 355 ms 836 KB Output is correct
3 Correct 347 ms 912 KB Output is correct
4 Correct 329 ms 848 KB Output is correct
5 Correct 346 ms 888 KB Output is correct
6 Correct 310 ms 764 KB Output is correct
7 Correct 343 ms 864 KB Output is correct
8 Correct 343 ms 840 KB Output is correct
9 Correct 338 ms 1016 KB Output is correct
10 Correct 346 ms 864 KB Output is correct
11 Correct 392 ms 960 KB Output is correct
12 Correct 330 ms 808 KB Output is correct
13 Correct 383 ms 900 KB Output is correct
14 Correct 391 ms 860 KB Output is correct
15 Correct 360 ms 872 KB Output is correct
16 Correct 341 ms 832 KB Output is correct
17 Correct 349 ms 864 KB Output is correct
18 Correct 365 ms 856 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 744 KB Output is correct
2 Correct 355 ms 836 KB Output is correct
3 Correct 347 ms 912 KB Output is correct
4 Correct 329 ms 848 KB Output is correct
5 Correct 346 ms 888 KB Output is correct
6 Correct 310 ms 764 KB Output is correct
7 Correct 343 ms 864 KB Output is correct
8 Correct 343 ms 840 KB Output is correct
9 Correct 338 ms 1016 KB Output is correct
10 Correct 346 ms 864 KB Output is correct
11 Correct 392 ms 960 KB Output is correct
12 Correct 330 ms 808 KB Output is correct
13 Correct 383 ms 900 KB Output is correct
14 Correct 391 ms 860 KB Output is correct
15 Correct 360 ms 872 KB Output is correct
16 Correct 341 ms 832 KB Output is correct
17 Correct 349 ms 864 KB Output is correct
18 Correct 365 ms 856 KB Output is correct
19 Correct 564 ms 19552 KB Output is correct
20 Correct 494 ms 17816 KB Output is correct
21 Incorrect 504 ms 19328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 744 KB Output is correct
2 Correct 355 ms 836 KB Output is correct
3 Correct 347 ms 912 KB Output is correct
4 Correct 329 ms 848 KB Output is correct
5 Correct 346 ms 888 KB Output is correct
6 Correct 310 ms 764 KB Output is correct
7 Correct 343 ms 864 KB Output is correct
8 Correct 343 ms 840 KB Output is correct
9 Correct 338 ms 1016 KB Output is correct
10 Correct 346 ms 864 KB Output is correct
11 Correct 392 ms 960 KB Output is correct
12 Correct 330 ms 808 KB Output is correct
13 Correct 383 ms 900 KB Output is correct
14 Correct 391 ms 860 KB Output is correct
15 Correct 360 ms 872 KB Output is correct
16 Correct 341 ms 832 KB Output is correct
17 Correct 349 ms 864 KB Output is correct
18 Correct 365 ms 856 KB Output is correct
19 Correct 334 ms 880 KB Output is correct
20 Correct 334 ms 900 KB Output is correct
21 Incorrect 342 ms 868 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 744 KB Output is correct
2 Correct 355 ms 836 KB Output is correct
3 Correct 347 ms 912 KB Output is correct
4 Correct 329 ms 848 KB Output is correct
5 Correct 346 ms 888 KB Output is correct
6 Correct 310 ms 764 KB Output is correct
7 Correct 343 ms 864 KB Output is correct
8 Correct 343 ms 840 KB Output is correct
9 Correct 338 ms 1016 KB Output is correct
10 Correct 346 ms 864 KB Output is correct
11 Correct 392 ms 960 KB Output is correct
12 Correct 330 ms 808 KB Output is correct
13 Correct 383 ms 900 KB Output is correct
14 Correct 391 ms 860 KB Output is correct
15 Correct 360 ms 872 KB Output is correct
16 Correct 341 ms 832 KB Output is correct
17 Correct 349 ms 864 KB Output is correct
18 Correct 365 ms 856 KB Output is correct
19 Correct 564 ms 19552 KB Output is correct
20 Correct 494 ms 17816 KB Output is correct
21 Incorrect 504 ms 19328 KB Output isn't correct
22 Halted 0 ms 0 KB -