Submission #708835

#	Time	Username	Problem	Language	Result	Execution time	Memory
708835		konstantys	Misspelling (JOI22_misspelling)	C++14	0 / 100	236 ms	155596 KiB

misspelling

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
long long a,b,n,m,tab[30],tab2[30],t[500005][30],k,k2,sum2,t2[2][500005];
vector<int> v[500005],v2[500005];
set<int> s1,s2;
int main(){
  ios_base::sync_with_stdio(0);
  cin>>n>>m;
  for(int i=0;i<n;i++) t2[0][i]=i,t2[1][i]=i;
  for(int i=0;i<m;i++){
    cin>>a>>b;
    a--,b--;
    if(a<b)
    t2[0][a]=max(t2[0][a],b);
    else if(b<a) t2[1][b]=max(t2[1][b],a);
  }
  for(int i=0;i<26;i++){
    t[n-1][i]=1;
    tab2[i]=1,tab[i]=1,sum2++;
  }
  for(int i=n-2;i>=0;i--){
    s2.insert(i+1);
    s1.insert(i+1);
    auto it=s1.begin();
    while(it!=s1.end() && (*it)<=t2[0][i]){ //nie może być malejacego
      for(int u=0;u<26;u++) tab2[u]-=t[(*it)][u],sum2-=t[(*it)][u];
      it=s1.erase(it);
    }
    it=s2.begin();
    while(it!=s2.end() && (*it)<=t2[1][i]){ //nie może być malejacego
      for(int u=0;u<26;u++) tab[u]-=t[(*it)][u];
      it=s2.erase(it);
    }
    k2=sum2;
    k=0;
    for(int u=0;u<26;u++){
      k2-=tab2[u];
      t[i][u]=1+k+k2;
      //cerr<<t[i][u]<<", ";
      k+=tab[u];
      tab2[u]+=t[i][u];
      sum2+=t[i][u];
      tab[u]+=t[i][u];
    }
  }
  m=0;
  for(int i=0;i<26;i++) m+=t[0][i];
  cout<<m;
  return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11