oj.uz

Submission #503443

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

const int MAX_N=8e5+10;
const ll mod=(1<<31);
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 350 ms 856 KB Output is correct
2 Correct 358 ms 840 KB Output is correct
3 Correct 344 ms 872 KB Output is correct
4 Correct 430 ms 968 KB Output is correct
5 Correct 355 ms 844 KB Output is correct
6 Correct 369 ms 860 KB Output is correct
7 Correct 351 ms 836 KB Output is correct
8 Correct 346 ms 824 KB Output is correct
9 Correct 406 ms 912 KB Output is correct
10 Correct 338 ms 876 KB Output is correct
11 Correct 358 ms 996 KB Output is correct
12 Correct 345 ms 876 KB Output is correct
13 Correct 362 ms 1084 KB Output is correct
14 Correct 341 ms 784 KB Output is correct
15 Correct 380 ms 1012 KB Output is correct
16 Correct 430 ms 840 KB Output is correct
17 Correct 400 ms 864 KB Output is correct
18 Correct 355 ms 876 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 856 KB Output is correct
2 Correct 358 ms 840 KB Output is correct
3 Correct 344 ms 872 KB Output is correct
4 Correct 430 ms 968 KB Output is correct
5 Correct 355 ms 844 KB Output is correct
6 Correct 369 ms 860 KB Output is correct
7 Correct 351 ms 836 KB Output is correct
8 Correct 346 ms 824 KB Output is correct
9 Correct 406 ms 912 KB Output is correct
10 Correct 338 ms 876 KB Output is correct
11 Correct 358 ms 996 KB Output is correct
12 Correct 345 ms 876 KB Output is correct
13 Correct 362 ms 1084 KB Output is correct
14 Correct 341 ms 784 KB Output is correct
15 Correct 380 ms 1012 KB Output is correct
16 Correct 430 ms 840 KB Output is correct
17 Correct 400 ms 864 KB Output is correct
18 Correct 355 ms 876 KB Output is correct
19 Correct 587 ms 19652 KB Output is correct
20 Correct 541 ms 17876 KB Output is correct
21 Incorrect 466 ms 19404 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 856 KB Output is correct
2 Correct 358 ms 840 KB Output is correct
3 Correct 344 ms 872 KB Output is correct
4 Correct 430 ms 968 KB Output is correct
5 Correct 355 ms 844 KB Output is correct
6 Correct 369 ms 860 KB Output is correct
7 Correct 351 ms 836 KB Output is correct
8 Correct 346 ms 824 KB Output is correct
9 Correct 406 ms 912 KB Output is correct
10 Correct 338 ms 876 KB Output is correct
11 Correct 358 ms 996 KB Output is correct
12 Correct 345 ms 876 KB Output is correct
13 Correct 362 ms 1084 KB Output is correct
14 Correct 341 ms 784 KB Output is correct
15 Correct 380 ms 1012 KB Output is correct
16 Correct 430 ms 840 KB Output is correct
17 Correct 400 ms 864 KB Output is correct
18 Correct 355 ms 876 KB Output is correct
19 Correct 381 ms 868 KB Output is correct
20 Correct 361 ms 900 KB Output is correct
21 Incorrect 340 ms 912 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 856 KB Output is correct
2 Correct 358 ms 840 KB Output is correct
3 Correct 344 ms 872 KB Output is correct
4 Correct 430 ms 968 KB Output is correct
5 Correct 355 ms 844 KB Output is correct
6 Correct 369 ms 860 KB Output is correct
7 Correct 351 ms 836 KB Output is correct
8 Correct 346 ms 824 KB Output is correct
9 Correct 406 ms 912 KB Output is correct
10 Correct 338 ms 876 KB Output is correct
11 Correct 358 ms 996 KB Output is correct
12 Correct 345 ms 876 KB Output is correct
13 Correct 362 ms 1084 KB Output is correct
14 Correct 341 ms 784 KB Output is correct
15 Correct 380 ms 1012 KB Output is correct
16 Correct 430 ms 840 KB Output is correct
17 Correct 400 ms 864 KB Output is correct
18 Correct 355 ms 876 KB Output is correct
19 Correct 587 ms 19652 KB Output is correct
20 Correct 541 ms 17876 KB Output is correct
21 Incorrect 466 ms 19404 KB Output isn't correct
22 Halted 0 ms 0 KB -