Submission #134305

#	Time	Username	Problem	Language	Result	Execution time	Memory
134305		Milki	Matching (CEOI11_mat)	C++14	100 / 100	883 ms	39512 KiB

mat

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7, baza = 1307, off = 1 << 20, MAXN = 1e6 + 5;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

struct Fenwick{
  ll t[MAXN];
  Fenwick(){ memset(t, 0, sizeof(t)); }

  void update(int x, int val){
    for(; x < MAXN; x += (x & (-x)))
      t[x] += val;
  }
  ll get(int x){
    ll ret = 0;
    for(; x > 0; x -= (x & (-x)))
      ret += t[x];
    return ret;
  }
  ll get(int l, int r){
    if(l) return get(r) - get(l - 1);
    return get(r);
  }
} Tsum, Tkth;

int n, m, pin[MAXN], p[MAXN], a[MAXN], pot[MAXN];
vector <int> v;

int get_pos(int x){
  return lower_bound(v.begin(), v.end(), x) - v.begin();
}

int nextint() {
    int ret = 0, d;
    d = getchar();
    while (d < 48 || d > 57)
       	d = getchar();
    do {
        ret = ret * 10 + d - 48;
        d = getchar();
    } while (d > 47 && d < 58);
    return ret;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  n = nextint(); m = nextint();
  REP(i, n){
    pin[i] = nextint();
    pin[i] --;
    p[ pin[i] ] = i;
  }
  REP(i, m){
    a[i] = nextint();
    v.pb(a[i]);
  }

  pot[0] = 1;
  FOR(i, 1, m)
    pot[i] = mul(pot[i - 1], baza);

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  REP(i, m)
    a[i] = get_pos(a[i]) + 1;

  vector <int> sol;

  int wanted = 0, hesh = 0;
  REP(i, n){
    wanted = add(wanted, mul(p[i], pot[i]));

    int pos = a[i];
    int smaller = Tkth.get(0, pos - 1);
    Tkth.update(pos, 1);
    hesh = add(hesh, mul(smaller, pot[i]));
    Tsum.update(pos, pot[i]);
    ll sum_bigger = Tsum.get(pos + 1, MAXN - 1) % mod;
    hesh = add(hesh, sum_bigger);
  }
  if(hesh == wanted)
    sol.pb(0);

  FOR(i, n, m){
    int pos = a[i - n];
    int smaller = Tkth.get(0, pos - 1);
    Tkth.update(pos, -1);
    Tsum.update(pos, -pot[i - n]);
    hesh = sub(hesh, mul(smaller, pot[i - n]));
    ll sum_bigger = Tsum.get(pos + 1, MAXN - 1) % mod;
    hesh = sub(hesh, sum_bigger);

    pos = a[i];
    smaller = Tkth.get(0, pos - 1);
    Tkth.update(pos, 1);
    Tsum.update(pos, pot[i]);
    hesh = add(hesh, mul(smaller, pot[i]));
    sum_bigger = Tsum.get(pos + 1, MAXN - 1) % mod;
    hesh = add(hesh, sum_bigger);

    wanted = mul(wanted, baza);
    if(wanted == hesh)
      sol.pb(i - n + 1);
  }

  cout << sz(sol) << "\n";
  for(auto it : sol)
    cout << it + 1 << " ";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10