Submission #134305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134305	2019-07-22T11:43:38 Z	Milki	Matching (CEOI11_mat)	C++14	100 / 100	883 ms	39512 KB

#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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	15992 KB	Output is correct
2	Correct	15 ms	15992 KB	Output is correct
3	Correct	15 ms	15992 KB	Output is correct
4	Correct	15 ms	15992 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	15992 KB	Output is correct
2	Correct	16 ms	15992 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	16504 KB	Output is correct
2	Correct	25 ms	16504 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	16504 KB	Output is correct
2	Correct	26 ms	16504 KB	Output is correct
3	Correct	17 ms	16120 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	20052 KB	Output is correct
2	Correct	108 ms	19820 KB	Output is correct
3	Correct	157 ms	20208 KB	Output is correct
4	Correct	160 ms	20100 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	20784 KB	Output is correct
2	Correct	160 ms	19820 KB	Output is correct
3	Correct	130 ms	20204 KB	Output is correct
4	Correct	121 ms	21992 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	20784 KB	Output is correct
2	Correct	115 ms	20400 KB	Output is correct
3	Correct	150 ms	20072 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	679 ms	31264 KB	Output is correct
2	Correct	883 ms	36680 KB	Output is correct
3	Correct	625 ms	26208 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	621 ms	30688 KB	Output is correct
2	Correct	854 ms	28768 KB	Output is correct
3	Correct	866 ms	36192 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	665 ms	30368 KB	Output is correct
2	Correct	519 ms	39512 KB	Output is correct
3	Correct	784 ms	28772 KB	Output is correct
4	Correct	506 ms	38232 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	603 ms	31072 KB	Output is correct
2	Correct	728 ms	29416 KB	Output is correct
3	Correct	260 ms	23528 KB	Output is correct
4	Correct	633 ms	36960 KB	Output is correct

Submission #134305

Compilation message