oj.uz

Submission #503440

# Submission time Handle Problem Language Result Execution time Memory
503440 2022-01-08T01:13:25 Z DanerZein Crossing (JOI21_crossing) C++14
3 / 100
 625 ms 23416 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]*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 373 ms 2252 KB Output is correct
2 Correct 348 ms 2284 KB Output is correct
3 Correct 353 ms 2412 KB Output is correct
4 Correct 330 ms 2224 KB Output is correct
5 Correct 345 ms 2200 KB Output is correct
6 Correct 321 ms 2284 KB Output is correct
7 Correct 409 ms 2192 KB Output is correct
8 Correct 395 ms 2324 KB Output is correct
9 Correct 475 ms 2292 KB Output is correct
10 Correct 454 ms 2248 KB Output is correct
11 Correct 414 ms 2308 KB Output is correct
12 Correct 354 ms 2300 KB Output is correct
13 Correct 367 ms 2288 KB Output is correct
14 Correct 340 ms 2304 KB Output is correct
15 Correct 339 ms 2312 KB Output is correct
16 Correct 338 ms 2396 KB Output is correct
17 Correct 335 ms 2284 KB Output is correct
18 Correct 361 ms 2420 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 2252 KB Output is correct
2 Correct 348 ms 2284 KB Output is correct
3 Correct 353 ms 2412 KB Output is correct
4 Correct 330 ms 2224 KB Output is correct
5 Correct 345 ms 2200 KB Output is correct
6 Correct 321 ms 2284 KB Output is correct
7 Correct 409 ms 2192 KB Output is correct
8 Correct 395 ms 2324 KB Output is correct
9 Correct 475 ms 2292 KB Output is correct
10 Correct 454 ms 2248 KB Output is correct
11 Correct 414 ms 2308 KB Output is correct
12 Correct 354 ms 2300 KB Output is correct
13 Correct 367 ms 2288 KB Output is correct
14 Correct 340 ms 2304 KB Output is correct
15 Correct 339 ms 2312 KB Output is correct
16 Correct 338 ms 2396 KB Output is correct
17 Correct 335 ms 2284 KB Output is correct
18 Correct 361 ms 2420 KB Output is correct
19 Correct 625 ms 23416 KB Output is correct
20 Correct 517 ms 21504 KB Output is correct
21 Incorrect 485 ms 22872 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 2252 KB Output is correct
2 Correct 348 ms 2284 KB Output is correct
3 Correct 353 ms 2412 KB Output is correct
4 Correct 330 ms 2224 KB Output is correct
5 Correct 345 ms 2200 KB Output is correct
6 Correct 321 ms 2284 KB Output is correct
7 Correct 409 ms 2192 KB Output is correct
8 Correct 395 ms 2324 KB Output is correct
9 Correct 475 ms 2292 KB Output is correct
10 Correct 454 ms 2248 KB Output is correct
11 Correct 414 ms 2308 KB Output is correct
12 Correct 354 ms 2300 KB Output is correct
13 Correct 367 ms 2288 KB Output is correct
14 Correct 340 ms 2304 KB Output is correct
15 Correct 339 ms 2312 KB Output is correct
16 Correct 338 ms 2396 KB Output is correct
17 Correct 335 ms 2284 KB Output is correct
18 Correct 361 ms 2420 KB Output is correct
19 Correct 335 ms 2280 KB Output is correct
20 Correct 359 ms 2240 KB Output is correct
21 Incorrect 340 ms 2280 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 2252 KB Output is correct
2 Correct 348 ms 2284 KB Output is correct
3 Correct 353 ms 2412 KB Output is correct
4 Correct 330 ms 2224 KB Output is correct
5 Correct 345 ms 2200 KB Output is correct
6 Correct 321 ms 2284 KB Output is correct
7 Correct 409 ms 2192 KB Output is correct
8 Correct 395 ms 2324 KB Output is correct
9 Correct 475 ms 2292 KB Output is correct
10 Correct 454 ms 2248 KB Output is correct
11 Correct 414 ms 2308 KB Output is correct
12 Correct 354 ms 2300 KB Output is correct
13 Correct 367 ms 2288 KB Output is correct
14 Correct 340 ms 2304 KB Output is correct
15 Correct 339 ms 2312 KB Output is correct
16 Correct 338 ms 2396 KB Output is correct
17 Correct 335 ms 2284 KB Output is correct
18 Correct 361 ms 2420 KB Output is correct
19 Correct 625 ms 23416 KB Output is correct
20 Correct 517 ms 21504 KB Output is correct
21 Incorrect 485 ms 22872 KB Output isn't correct
22 Halted 0 ms 0 KB -