Submission #134293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134293	2019-07-22T11:16:45 Z	Milki	Matching (CEOI11_mat)	C++14	63 / 100	2000 ms	52932 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{
  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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	17016 KB	Output is correct
2	Correct	16 ms	16760 KB	Output is correct
3	Correct	16 ms	16760 KB	Output is correct
4	Correct	16 ms	16760 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	16888 KB	Output is correct
2	Correct	18 ms	16888 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	17272 KB	Output is correct
2	Correct	45 ms	17308 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	17400 KB	Output is correct
2	Correct	48 ms	17404 KB	Output is correct
3	Correct	21 ms	16952 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	304 ms	20848 KB	Output is correct
2	Correct	347 ms	20592 KB	Output is correct
3	Correct	529 ms	22008 KB	Output is correct
4	Correct	516 ms	21868 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	21616 KB	Output is correct
2	Correct	576 ms	21232 KB	Output is correct
3	Correct	357 ms	21584 KB	Output is correct
4	Correct	346 ms	22756 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	21744 KB	Output is correct
2	Correct	340 ms	21232 KB	Output is correct
3	Correct	423 ms	21228 KB	Output is correct

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1986 ms	41296 KB	Output is correct
2	Execution timed out	2058 ms	52932 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1739 ms	40924 KB	Output is correct
2	Execution timed out	2037 ms	35424 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2056 ms	38216 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1898 ms	39228 KB	Output is correct
2	Execution timed out	2060 ms	39268 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Submission #134293

Compilation message