oj.uz

Submission #503439

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

const int MAX_N=2e5+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]*31);
    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 354 ms 2356 KB Output is correct
2 Correct 342 ms 2420 KB Output is correct
3 Correct 390 ms 2328 KB Output is correct
4 Correct 332 ms 2288 KB Output is correct
5 Correct 363 ms 2336 KB Output is correct
6 Correct 365 ms 2320 KB Output is correct
7 Correct 363 ms 2320 KB Output is correct
8 Correct 365 ms 2416 KB Output is correct
9 Correct 347 ms 2520 KB Output is correct
10 Correct 447 ms 2332 KB Output is correct
11 Correct 364 ms 2436 KB Output is correct
12 Correct 350 ms 2376 KB Output is correct
13 Correct 425 ms 2372 KB Output is correct
14 Correct 341 ms 2368 KB Output is correct
15 Correct 387 ms 2492 KB Output is correct
16 Correct 339 ms 2336 KB Output is correct
17 Correct 400 ms 2356 KB Output is correct
18 Correct 357 ms 2340 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 2356 KB Output is correct
2 Correct 342 ms 2420 KB Output is correct
3 Correct 390 ms 2328 KB Output is correct
4 Correct 332 ms 2288 KB Output is correct
5 Correct 363 ms 2336 KB Output is correct
6 Correct 365 ms 2320 KB Output is correct
7 Correct 363 ms 2320 KB Output is correct
8 Correct 365 ms 2416 KB Output is correct
9 Correct 347 ms 2520 KB Output is correct
10 Correct 447 ms 2332 KB Output is correct
11 Correct 364 ms 2436 KB Output is correct
12 Correct 350 ms 2376 KB Output is correct
13 Correct 425 ms 2372 KB Output is correct
14 Correct 341 ms 2368 KB Output is correct
15 Correct 387 ms 2492 KB Output is correct
16 Correct 339 ms 2336 KB Output is correct
17 Correct 400 ms 2356 KB Output is correct
18 Correct 357 ms 2340 KB Output is correct
19 Runtime error 26 ms 9988 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 2356 KB Output is correct
2 Correct 342 ms 2420 KB Output is correct
3 Correct 390 ms 2328 KB Output is correct
4 Correct 332 ms 2288 KB Output is correct
5 Correct 363 ms 2336 KB Output is correct
6 Correct 365 ms 2320 KB Output is correct
7 Correct 363 ms 2320 KB Output is correct
8 Correct 365 ms 2416 KB Output is correct
9 Correct 347 ms 2520 KB Output is correct
10 Correct 447 ms 2332 KB Output is correct
11 Correct 364 ms 2436 KB Output is correct
12 Correct 350 ms 2376 KB Output is correct
13 Correct 425 ms 2372 KB Output is correct
14 Correct 341 ms 2368 KB Output is correct
15 Correct 387 ms 2492 KB Output is correct
16 Correct 339 ms 2336 KB Output is correct
17 Correct 400 ms 2356 KB Output is correct
18 Correct 357 ms 2340 KB Output is correct
19 Correct 380 ms 2252 KB Output is correct
20 Correct 442 ms 2228 KB Output is correct
21 Incorrect 353 ms 2444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 2356 KB Output is correct
2 Correct 342 ms 2420 KB Output is correct
3 Correct 390 ms 2328 KB Output is correct
4 Correct 332 ms 2288 KB Output is correct
5 Correct 363 ms 2336 KB Output is correct
6 Correct 365 ms 2320 KB Output is correct
7 Correct 363 ms 2320 KB Output is correct
8 Correct 365 ms 2416 KB Output is correct
9 Correct 347 ms 2520 KB Output is correct
10 Correct 447 ms 2332 KB Output is correct
11 Correct 364 ms 2436 KB Output is correct
12 Correct 350 ms 2376 KB Output is correct
13 Correct 425 ms 2372 KB Output is correct
14 Correct 341 ms 2368 KB Output is correct
15 Correct 387 ms 2492 KB Output is correct
16 Correct 339 ms 2336 KB Output is correct
17 Correct 400 ms 2356 KB Output is correct
18 Correct 357 ms 2340 KB Output is correct
19 Runtime error 26 ms 9988 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -