Submission #708837

#	Time	Username	Problem	Language	Result	Execution time	Memory
708837		konstantys	Misspelling (JOI22_misspelling)	C++14	100 / 100	468 ms	191748 KiB

misspelling

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<set>
#define MOD 1000000007LL
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]+=MOD-t[(*it)][u],sum2+=MOD-t[(*it)][u];
      it=s1.erase(it);
    }
    sum2%=MOD;
    for(int u=0;u<26;u++) tab2[u]%=MOD;
    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]+=MOD-t[(*it)][u];
      it=s2.erase(it);
    }
    for(int u=0;u<26;u++) tab[u]%=MOD;
    k2=sum2;
    k=0;
    for(int u=0;u<26;u++){
      k2+=MOD-tab2[u],k2%=MOD;
      t[i][u]=1+k+k2,t[i][u]%=MOD;
      //cerr<<t[i][u]<<", ";
      k+=tab[u],k%=MOD;
      tab2[u]+=t[i][u],tab2[u]%=MOD;
      sum2+=t[i][u],sum2%=MOD;
      tab[u]+=t[i][u],tab[u]%=MOD;
    }
  }
  m=0;
  for(int i=0;i<26;i++) m+=t[0][i],m%=MOD;
  cout<<m;
  return 0;
}

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