Submission #134298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134298	2019-07-22T11:29:06 Z	Milki	Matching (CEOI11_mat)	C++14	100 / 100	1807 ms	65536 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 Tournament{
  ll t[2 * off];
  Tournament(){ memset(t, 0, sizeof(t)); }

  void update(int x, int val){
    x += off; t[x] = val;
    for(x >>= 1; x > 0; x >>= 1)
      t[x] = t[x * 2] + t[x * 2 + 1];
  }
  ll 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 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 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]);

  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(1, 0, off, 0, pos);
    Tkth.update(pos, 1);
    hesh = add(hesh, mul(smaller, pot[i]));
    Tsum.update(pos, pot[i]);
    ll sum_bigger = Tsum.get(1, 0, off, pos + 1, off) % 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(1, 0, off, 0, pos);
    Tkth.update(pos, 0);
    Tsum.update(pos, 0);
    hesh = sub(hesh, mul(smaller, pot[i - n]));
    ll sum_bigger = Tsum.get(1, 0, off, pos + 1, off) % mod;
    hesh = sub(hesh, sum_bigger);

    pos = a[i];
    smaller = Tkth.get(1, 0, off, 0, pos);
    Tkth.update(pos, 1);
    Tsum.update(pos, pot[i]);
    hesh = add(hesh, mul(smaller, pot[i]));
    sum_bigger = Tsum.get(1, 0, off, pos + 1, off) % 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	31 ms	33144 KB	Output is correct
2	Correct	29 ms	33272 KB	Output is correct
3	Correct	30 ms	33144 KB	Output is correct
4	Correct	34 ms	33272 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	33276 KB	Output is correct
2	Correct	31 ms	33272 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	33784 KB	Output is correct
2	Correct	47 ms	33728 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	33768 KB	Output is correct
2	Correct	48 ms	33656 KB	Output is correct
3	Correct	33 ms	33256 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	212 ms	36616 KB	Output is correct
2	Correct	211 ms	36368 KB	Output is correct
3	Correct	414 ms	36800 KB	Output is correct
4	Correct	401 ms	36716 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	238 ms	37176 KB	Output is correct
2	Correct	361 ms	36400 KB	Output is correct
3	Correct	230 ms	36720 KB	Output is correct
4	Correct	218 ms	38692 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	37152 KB	Output is correct
2	Correct	215 ms	36608 KB	Output is correct
3	Correct	265 ms	36588 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1174 ms	47980 KB	Output is correct
2	Correct	1469 ms	53336 KB	Output is correct
3	Correct	1301 ms	50348 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1046 ms	47348 KB	Output is correct
2	Correct	1807 ms	45536 KB	Output is correct
3	Correct	1503 ms	65536 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1247 ms	47236 KB	Output is correct
2	Correct	927 ms	62800 KB	Output is correct
3	Correct	1590 ms	55336 KB	Output is correct
4	Correct	755 ms	65536 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1140 ms	47860 KB	Output is correct
2	Correct	1456 ms	46112 KB	Output is correct
3	Correct	509 ms	44108 KB	Output is correct
4	Correct	916 ms	65536 KB	Output is correct

Submission #134298

Compilation message