oj.uz

Submission #886179

# Submission time Handle Problem Language Result Execution time Memory
886179 2023-12-11T14:22:29 Z nguyentunglam Teams (IOI15_teams) C++17
100 / 100
 1428 ms 152164 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5e5 + 10;

pair<int, int> a[N];

int n;

int last[N], pref[N], timer[N];

struct node {
  int left, right, sum;
};

node T[N * 20 + 10];

int cnt, it[N], idx[N];

vector<pair<int, int> > rrh;

void up(int s, int l, int r, int pos, int val) {
  if (l == r) {
    T[s].sum += val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) {
    T[++cnt] = T[T[s].left];
    T[s].left = cnt;
    up(T[s].left, l, mid, pos, val);
  }
  else {
    T[++cnt] = T[T[s].right];
    T[s].right = cnt;
    up(T[s].right, mid + 1, r, pos, val);
  }
  T[s].sum = T[T[s].left].sum + T[T[s].right].sum;
}

int get(int s, int l, int r, int from, int to) {
  if (l > to || r < from || !s) return 0;
  if (from <= l && r <= to) return T[s].sum;
  int mid = l + r >> 1;
  return get(T[s].left, l, mid, from, to) + get(T[s].right, mid + 1, r, from, to);
}

int tree_idx (int x) {
  return upper_bound(all(rrh), make_pair(x, 0)) - rrh.begin() + 1;
}

void init(int _n, int A[], int B[]) {
  n = _n;

  for(int i = 1; i <= n; i++) {
    a[i] = make_pair(A[i - 1], B[i - 1]);
  }

  sort(a + 1, a + n + 1);

  for(int i = 1; i <= n; i++) {
    rrh.emplace_back(a[i].second, i);
  }

  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());

  for(int i = 1; i <= n; i++) {
    int old = a[i].second;
    a[i].second = upper_bound(all(rrh), make_pair(a[i].second, i)) - rrh.begin();
    idx[old] = max(idx[old], a[i].second);
  }

  for(int i = 1; i <= n; i++) {
    if (idx[i] == 0) idx[i] = idx[i - 1];
  }

  for(int i = 1, j = 1; i <= n; i++) {
    T[it[i] = ++cnt] =  T[it[i - 1]];
    while (j <= n && a[j].first == i) {
      up(it[i], 1, n, a[j].second, 1);
      j++;
    }
  }

//  for(int i = 1; i <= n; i++) cout << a[i].first << " " << a[i].second << endl;
}

int can (int m, int k[]) {
  sort(k, k + m);
  for(int i = 0, p = 0; i < m; i++) {
    int sz = k[i];

    auto calc = [&] (int x) {
      int total = get(it[sz], 1, n, 1, x);
      int lost = 0;
      if (!p) return total;
      int l = 1, r = p, pos = 0;
      while (l <= r) {
        int mid = l + r >> 1;
        if (last[mid] >= x) {
          pos = mid;
          l = mid + 1;
        } else r = mid - 1;
      }
      lost = pref[p] - pref[pos];
      if (pos) {
        last[p + 1] = 0;
        lost += get(it[timer[pos]], 1, n, last[pos + 1] + 1, x);
      }
      return total - lost;
    };
//    if (i == 1) cout << calc(1) << endl;

//    if (i == 0) {
//      cout << calc(1) << endl;
//      return 0;
//    }

    int not_use = calc(idx[sz - 1]);
//    if (i == 0) cout << calc(1) << endl;
//    if (i == 0) {
//      cout << sz - 1 << endl;
//      cout << idx[sz - 1] << endl;
//      cout << not_use << endl;
//    }
    int l = 1, r = n, smallest = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (calc(mid) - not_use >= sz) {
        smallest = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
//    cout << smallest << endl;
//    cout << calc(smallest) << " " << not_use << endl;
    if (!smallest) return 0;
    while (p && last[p] <= smallest) p--;
    if (p) {
      pref[p] = get(it[timer[p]], 1, n, smallest + 1, last[p]);
      if (p) pref[p] += pref[p - 1];
    }
    ++p;
    pref[p] = pref[p - 1] + get(it[sz], 1, n, 1, smallest);
    last[p] = smallest;
    timer[p] = sz;
  }
  return 1;
}

#ifdef ngu
int32_t main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int n; cin >> n;

  int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
  int *B = (int *)malloc(sizeof(int) * (unsigned int)N);

  for(int i = 0; i < n; i++) cin >> A[i] >> B[i];

  init(n, A, B);

  int q; cin >> q;

  while (q--) {
    int m; cin >> m;
    int *k = (int *)malloc(sizeof(int) * (unsigned int)m);
    for(int i = 0; i < m; i++) cin >> k[i];
    cout << can(m, k) << endl;
  }

}
#endif // ngu

Compilation message

teams.cpp: In function 'void up(int, int, int, int, int)':
teams.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = l + r >> 1;
      |             ~~^~~
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = l + r >> 1;
      |             ~~^~~
teams.cpp: In function 'int tree_idx(int)':
teams.cpp:54:63: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   54 |   return upper_bound(all(rrh), make_pair(x, 0)) - rrh.begin() + 1;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:75:68: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   75 |     a[i].second = upper_bound(all(rrh), make_pair(a[i].second, i)) - rrh.begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In lambda function:
teams.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid = l + r >> 1;
      |                   ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:134:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |       int mid = l + r >> 1;
      |                 ~~^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 30920 KB Output is correct
2 Correct 57 ms 31012 KB Output is correct
3 Correct 54 ms 29028 KB Output is correct
4 Correct 56 ms 31532 KB Output is correct
5 Correct 35 ms 30664 KB Output is correct
6 Correct 34 ms 30660 KB Output is correct
7 Correct 33 ms 30660 KB Output is correct
8 Correct 33 ms 30740 KB Output is correct
9 Correct 107 ms 30832 KB Output is correct
10 Correct 61 ms 30332 KB Output is correct
11 Correct 33 ms 30400 KB Output is correct
12 Correct 30 ms 30672 KB Output is correct
13 Correct 39 ms 30724 KB Output is correct
14 Correct 39 ms 28872 KB Output is correct
15 Correct 48 ms 30936 KB Output is correct
16 Correct 58 ms 30932 KB Output is correct
17 Correct 35 ms 30904 KB Output is correct
18 Correct 37 ms 30920 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 31684 KB Output is correct
2 Correct 61 ms 31688 KB Output is correct
3 Correct 281 ms 35012 KB Output is correct
4 Correct 54 ms 31432 KB Output is correct
5 Correct 210 ms 31320 KB Output is correct
6 Correct 188 ms 31248 KB Output is correct
7 Correct 40 ms 31320 KB Output is correct
8 Correct 149 ms 31380 KB Output is correct
9 Correct 105 ms 30828 KB Output is correct
10 Correct 204 ms 30932 KB Output is correct
11 Correct 202 ms 30916 KB Output is correct
12 Correct 265 ms 31116 KB Output is correct
13 Correct 285 ms 31696 KB Output is correct
14 Correct 313 ms 33492 KB Output is correct
15 Correct 147 ms 31688 KB Output is correct
16 Correct 152 ms 31756 KB Output is correct
17 Correct 152 ms 31560 KB Output is correct
18 Correct 146 ms 31708 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 145356 KB Output is correct
2 Correct 400 ms 145344 KB Output is correct
3 Correct 1228 ms 152164 KB Output is correct
4 Correct 380 ms 145124 KB Output is correct
5 Correct 637 ms 142776 KB Output is correct
6 Correct 636 ms 142780 KB Output is correct
7 Correct 183 ms 142556 KB Output is correct
8 Correct 542 ms 142756 KB Output is correct
9 Correct 640 ms 142924 KB Output is correct
10 Correct 677 ms 141064 KB Output is correct
11 Correct 849 ms 141864 KB Output is correct
12 Correct 834 ms 142524 KB Output is correct
13 Correct 1136 ms 144320 KB Output is correct
14 Correct 1428 ms 149152 KB Output is correct
15 Correct 563 ms 145336 KB Output is correct
16 Correct 626 ms 145496 KB Output is correct
17 Correct 519 ms 144856 KB Output is correct
18 Correct 510 ms 144700 KB Output is correct