Submission #134293

#	Time	Username	Problem	Language	Result	Execution time	Memory
134293		Milki	Matching (CEOI11_mat)	C++14	63 / 100	2060 ms	52932 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 Tournament{
  int t[2 * off];
  Tournament(){ memset(t, 0, sizeof(t)); }

  void update(int x, int lo, int hi, int a, int b, int val){
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b) { t[x] = val; return; }
    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b, val); update(x * 2 + 1, mid, hi, a, b, val);
    t[x] = add(t[x * 2], t[x * 2 + 1]);
  }
  int get(int x, int lo, int hi, int a, int b){
    if(lo >= b || hi <= a) return 0;
    if(lo >= a && hi <= b) return t[x];
    int mid = (lo + hi) >> 1;
    return add(get(x * 2, lo, mid, a, b),
               get(x * 2 + 1, mid, hi, a, b));
  }
} 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 main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> m;
  REP(i, n){
    cin >> pin[i];
    pin[i] --;
    p[ pin[i] ] = i;
  }
  REP(i, m){
    cin >> a[i];
    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());

  vector <int> sol;

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

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

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

    pos = get_pos(a[i]);
    smaller = Tkth.get(1, 0, off, 0, pos);
    Tkth.update(1, 0, off, pos, pos + 1, 1);
    Tsum.update(1, 0, off, pos, pos + 1, pot[i]);
    hesh = add(hesh, mul(smaller, pot[i]));
    sum_bigger = Tsum.get(1, 0, off, pos + 1, off);
    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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10