Submission #687686

#	Time	Username	Problem	Language	Result	Execution time	Memory
687686		tvladm2009	Teams (IOI15_teams)	C++17	0 / 100	1154 ms	391284 KiB

teams

#include <bits/stdc++.h>

struct Interval {
  int l;
  int r;
  int pos;
};

using namespace std;

typedef long long ll;
const int N = (int) 5e5 + 7;
const int Q = (int) 2e5 + 7;
pair<int, int> a[N];
vector<int> pos[N];
int n, q;

struct Node {
  Node *left;
  Node *right;
  int sum;

  Node() {
    left = NULL;
    right = NULL;
    sum = 0;
  }
};

Node *segt[N];

void build(Node *root, int tl, int tr) {
  if (tl == tr) {
    root->sum = 0;
  } else {
    root->left = new Node();
    root->right = new Node();
    int tm = (tl + tr) / 2;
    build(root->left, tl, tm);
    build(root->right, tm + 1, tr);
    root->sum = root->left->sum + root->right->sum;
  }
}

void update(Node *root, Node *prev, int tl, int tr, int pos, int val) {
  if (tl == tr) {
    root->sum += val;
  } else {
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
      root->left = new Node();
      root->right = prev->right;
      update(root->left, prev->left, tl, tm, pos, val);
    } else {
      root->left = prev->left;
      root->right = new Node();
      update(root->right, prev->right, tm + 1, tr, pos, val);
    }
    root->sum = root->left->sum + root->right->sum;
  }
}

int query(Node *root, int tl, int tr, int l, int r) {
  if (l <= tl && tr <= r) {
    return root->sum;
  }
  int tm = (tl + tr) / 2;
  if (l <= tm && r <= tm) {
    return query(root->left, tl, tm, l, r);
  } else if (tm + 1 <= l && tm + 1 <= r) {
    return query(root->right, tm + 1, tr, l, r);
  } else {
    return query(root->left, tl, tm, l, tm) + query(root->right, tm + 1, tr, tm + 1, r);
  }
}

int getkth(int l, int r, int k) {
  int low = 0, high = n, ret = 0;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (query(segt[mid], 1, n, l, r) < k) {
      ret = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return ret + 1;
}

void init(int N, int A[], int B[]) {
  n = N;
  for (int i = 1; i <= n; i++) {
    a[i].first = A[i - 1];
    a[i].second = B[i - 1];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    pos[a[i].second].push_back(i);
  }
  segt[0] = new Node();
  build(segt[0], 1, n);
  for (int i = 1; i <= n; i++) {
    segt[i] = new Node();
    if ((int) pos[i].size() == 0) segt[i] = segt[i - 1];
    for (auto &it : pos[i]) {
      update(segt[i], segt[i - 1], 1, n, it, 1);
    }
  }
}

int can(int M, int K[]) {
  q = M;
  vector<int> queries(q + 1);
  for (int i = 1; i <= q; i++) {
    queries[i] = K[i - 1];
  }
  sort(queries.begin(), queries.end());
  int j = 1;
  vector<Interval> st;
  for (int i = 1; i <= q; i++) {
    int low = 0, high = n, ret = 0;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (a[mid].first <= queries[i]) {
        ret = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    ret++;
    if (j < ret) st.push_back({j, ret - 1, 0});
    j = ret;
    int aux = queries[i];
    while (aux > 0) {
      if ((int) st.size() == 1) {
        st[0].pos = max(st[0].pos, query(segt[queries[i] - 1], 1, n, st[0].l, st[0].r));
        if (st[0].pos + aux <= (st[0].r - st[0].l + 1)) {
          st[0].pos += aux;
          aux = 0;
          break;
        } else {
          return false;
        }
      } else {
        st[(int) st.size() - 1].pos = max(st[(int) st.size() - 1].pos, query(segt[queries[i] - 1], 1, n, st[(int) st.size() - 1].l, st[(int) st.size() - 1].r));
        st[(int) st.size() - 2].pos = max(st[(int) st.size() - 2].pos, query(segt[queries[i] - 1], 1, n, st[(int) st.size() - 2].l, st[(int) st.size() - 2].r));
        int kth = getkth(st[(int) st.size() - 2].l, st[(int) st.size() - 2].r, st[(int) st.size() - 2].pos);
        int newadded = max(0, query(segt[kth - 1], 1, n, st[(int) st.size() - 1].l, st[(int) st.size() - 1].r) - st[(int) st.size() - 1].pos);
        if (newadded <= aux) {
          st[(int) st.size() - 2].pos += st[(int) st.size() - 1].pos + newadded;
          st[(int) st.size() - 2].r = st[(int) st.size() - 1].r;
          st.pop_back();
          aux -= newadded;
        } else {
          st[(int) st.size() - 1].pos += aux;
          aux = 0;
        }
      }
    }
  }
  return true;
}

Compilation message (stderr)

teams.cpp: In function 'void update(Node*, Node*, int, int, int, int)':
teams.cpp:45:57: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   45 | void update(Node *root, Node *prev, int tl, int tr, int pos, int val) {
      |                                                     ~~~~^~~
teams.cpp:15:13: note: shadowed declaration is here
   15 | vector<int> pos[N];
      |             ^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   91 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:12:11: note: shadowed declaration is here
   12 | const int N = (int) 5e5 + 7;
      |           ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23