Submission #555679

#	Time	Username	Problem	Language	Result	Execution time	Memory
555679		600Mihnea	Misspelling (JOI22_misspelling)	C++17	100 / 100	958 ms	204428 KiB

misspelling

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

const int M = (int) 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) {
      r = mul(r, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

int dv(int a, int b) {
  return mul(a, pw(b, M - 2));
}

void addup(int &a,int b){
  a=add(a,b);
}

void mulup(int &a,int b){
  a=mul(a,b);
}

struct Interval {
  int l;
  int r;
  int what_first;
};

const int N=(int)5e5+7;
int n,m;
int dp[N][30][2];
int transfer[N][30];
Interval dt[N];
int cnt_good;
int vals[N];

void gen(int pos) {
  if(pos>n){
    assert(pos==n+1);
    bool is_ok=1;
    for (int k=1;k<=m;k++){
      int l=dt[k].l,r=dt[k].r;
      int what_is=-1;
      for (int it=l;it<=r;it++){
        if(vals[it]!=vals[it+1]){
          what_is=(vals[it]<vals[it+1]);
          break;
        }
      }
      if(what_is==-1) continue;
      if(what_is!=dt[k].what_first) {
        is_ok=0;
      }
    }
    if(!is_ok) return;
    cout<<++cnt_good<<" : ";
    for (int i=1;i<=n;i++){
      cout<<vals[i]<<" ";
    }
    cout<<"\n";
    return;
  }
  for (int ch=0;ch<26;ch++){
    vals[pos]=ch;
    gen(pos+1);
  }
}

void compute_row(int i){
  if(i>0) {
    for(int x=0;x<30;x++){
      addup(transfer[i][x],transfer[i-1][x]);
    }
  }
  int cur=0;
  for (int x=0;x<27;x++){
    addup(cur,dp[i][x][0]);
    addup(transfer[i][x+1],cur);
  }
  cur=0;
  for(int x=27;x>=1;x--){
    addup(cur,dp[i][x][1]);
    addup(transfer[i][x-1],cur);
  }
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif
  home = 0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }
  ios::sync_with_stdio(0); cin.tie(0);

  cin>>n>>m;
  vector<pair<int, int>> in,out;

  for(int i=1;i<=m;i++){
    int l,r;
    cin>>l>>r;
    int what=0;
    if(l>r){
      swap(l,r);
      what=1;
    }
    assert(l<r);
    r--;
    assert(l<=r);
    dt[i]={l, r, what};

    in.push_back({l, i});
    out.push_back({r+1, i});
  }
  sort(in.begin(), in.end());
  sort(out.begin(), out.end());

  assert((int)in.size()==m);
  assert((int)out.size()==m);

  int pin=0;
  int pout=0;

  ///gen(1);
  dp[0][26][1]=1;
  multiset<int> s0, s1;
  compute_row(0);
  for (int i=1;i<=n;i++){
    while(pin<(int)in.size()&&in[pin].first==i){
      int k=in[pin++].second;
      if(dt[k].what_first==0) s0.insert(dt[k].l); else s1.insert(dt[k].l);
    }
    while(pout<(int)out.size()&&out[pout].first==i){
      int k=out[pout++].second;
      if(dt[k].what_first==0) s0.erase(s0.find(dt[k].l)); else s1.erase(s1.find(dt[k].l));
    }
    int m0=0,m1=0;
    if(!s0.empty()){
      auto it=s0.end();
      it--;
      m0=*it;
    }

    if(!s1.empty()){
      auto it=s1.end();
      it--;
      m1=*it;
    }
    for (int x=0;x<26;x++) {
      /// compute dp[i][x][??]
      int start=min(m0,m1)+1;
      int start2=max(m0,m1)+1;
      int finish=max(m0,m1);

      if(start2<=i){
        if(start2-2<0) addup(dp[i][x][0], transfer[i-1][x]), addup(dp[i][x][1],transfer[i-1][x]); else
        addup(dp[i][x][0],add(transfer[i-1][x],-transfer[start2-2][x])),
        addup(dp[i][x][1],add(transfer[i-1][x],-transfer[start2-2][x]));
      }

      if(start<=finish){
        if(start-2<0)
        addup(dp[i][x][m0<m1],transfer[finish-1][x]); else
        addup(dp[i][x][m0<m1],add(transfer[finish-1][x],-transfer[start-2][x]));
      }
    }
    compute_row(i);
  }
  assert(pin==m);
  assert(pout==m);
  int sol=0;
  for (int x=0;x<26;x++){
    addup(sol,dp[n][x][0]);
    ///addup(sol,dp[n][x][1]);
  }
  cout<<sol<<"\n";
}
/**
1 x x
y y 3

x 2 x
y y 3
**/

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:121:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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