oj.uz

Submission #726909

# Submission time Handle Problem Language Result Execution time Memory
726909 2023-04-19T14:18:51 Z Alex_tz307 Teams (IOI15_teams) C++17
100 / 100
 2614 ms 381132 KB 
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

struct node {
  int sum;
  node* l;
  node* r;

  node() : sum(0), l(nullptr), r(nullptr) {}
};

const int kN = 5e5;
int n, ver[1 + kN], used[kN];
node *roots[1 + kN];
vector<int> rEnd[1 + kN];
vector<pair<int, int>> intervals;

void build(node *root, int lx, int rx) {
  if (lx == rx) {
    return;
  }

  int mid = (lx + rx) / 2;

  root->l = new node;
  build(root->l, lx, mid);

  root->r = new node;
  build(root->r, mid + 1, rx);
}

void update(node *prev, node *curr, int lx, int rx, int pos) {
  if (lx == rx) {
    curr->sum = prev->sum + 1;
    return;
  }

  int mid = (lx + rx) / 2;

  if (pos <= mid) {
    curr->l = new node;
    curr->r = prev->r;
    update(prev->l, curr->l, lx, mid, pos);
  } else {
    curr->l = prev->l;
    curr->r = new node;
    update(prev->r, curr->r, mid + 1, rx, pos);
  }

  curr->sum = curr->l->sum + curr->r->sum;
}

int query(node *root, int lx, int rx, int st, int dr) {
  if (st <= lx && rx <= dr) {
    return root->sum;
  }

  int mid = (lx + rx) / 2;

  int sum = 0;

  if (st <= mid) {
    sum += query(root->l, lx, mid, st, dr);
  }

  if (mid < dr) {
    sum += query(root->r, mid + 1, rx, st, dr);
  }

  return sum;
}

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

  for (int i = 0; i < N; ++i) {
    rEnd[A[i]].emplace_back(B[i]);
  }

  roots[0] = new node;
  build(roots[0], 1, n);

  int version = 0;

  for (int l = 1; l <= n; ++l) {
    for (const int &r : rEnd[l]) {
      version += 1;
      roots[version] = new node;
      update(roots[version - 1], roots[version], 1, n, r);
    }

    ver[l] = version;
  }
}

int can(int m, int a[]) {
  int sum = 0;

  for (int i = 0; i < m; ++i) {
    sum += a[i];
    if (n < sum) {
      return 0;
    }
  }

  sort(a, a + m);

  intervals.clear();

  int last = a[0];

  for (int i = 1; i < m; ++i) {
    if (last != a[i]) {
      intervals.emplace_back(last, a[i] - 1);
    }
    last = a[i];
  }

  intervals.emplace_back(last, n);

  int R = intervals.size();

  for (int i = 0; i < R; ++i) {
    used[i] = 0;
  }

  int ptr = 0;

  for (int i = 0; i < m; ++i) {
    int j = i;

    while (j < m && a[i] == a[j]) {
      j += 1;
    }

    int req = a[i] * (j - i);

    for (int k = ptr; k < R && req; ++k) {
      int take = min(req, query(roots[ver[a[i]]], 1, n, intervals[k].first, intervals[k].second) - used[k]);
      req -= take;
      used[k] += take;
    }

    if (req) {
      return 0;
    }

    i = j - 1;
    ptr += 1;
  }

  return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:123:25: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  123 |   int R = intervals.size();
      |           ~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11996 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12008 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 9 ms 11988 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 12064 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 7 ms 12072 KB Output is correct
20 Correct 6 ms 11988 KB Output is correct
21 Correct 7 ms 11988 KB Output is correct
22 Correct 6 ms 11960 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 7 ms 12040 KB Output is correct
25 Correct 7 ms 11988 KB Output is correct
26 Correct 7 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 77420 KB Output is correct
2 Correct 134 ms 77464 KB Output is correct
3 Correct 150 ms 77432 KB Output is correct
4 Correct 133 ms 77828 KB Output is correct
5 Correct 81 ms 76208 KB Output is correct
6 Correct 84 ms 76260 KB Output is correct
7 Correct 83 ms 76216 KB Output is correct
8 Correct 88 ms 76236 KB Output is correct
9 Correct 76 ms 73948 KB Output is correct
10 Correct 79 ms 73944 KB Output is correct
11 Correct 99 ms 76996 KB Output is correct
12 Correct 86 ms 73904 KB Output is correct
13 Correct 89 ms 77076 KB Output is correct
14 Correct 94 ms 75332 KB Output is correct
15 Correct 119 ms 77228 KB Output is correct
16 Correct 127 ms 77260 KB Output is correct
17 Correct 84 ms 77084 KB Output is correct
18 Correct 95 ms 77040 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 77804 KB Output is correct
2 Correct 160 ms 77836 KB Output is correct
3 Correct 207 ms 80784 KB Output is correct
4 Correct 124 ms 77852 KB Output is correct
5 Correct 107 ms 76620 KB Output is correct
6 Correct 103 ms 76644 KB Output is correct
7 Correct 97 ms 76596 KB Output is correct
8 Correct 99 ms 76560 KB Output is correct
9 Correct 76 ms 73948 KB Output is correct
10 Correct 90 ms 74228 KB Output is correct
11 Correct 106 ms 77316 KB Output is correct
12 Correct 828 ms 74328 KB Output is correct
13 Correct 264 ms 77612 KB Output is correct
14 Correct 241 ms 78928 KB Output is correct
15 Correct 147 ms 77772 KB Output is correct
16 Correct 145 ms 77724 KB Output is correct
17 Correct 106 ms 77492 KB Output is correct
18 Correct 100 ms 77384 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 375236 KB Output is correct
2 Correct 883 ms 375256 KB Output is correct
3 Correct 1240 ms 381132 KB Output is correct
4 Correct 838 ms 375364 KB Output is correct
5 Correct 472 ms 368928 KB Output is correct
6 Correct 450 ms 368908 KB Output is correct
7 Correct 439 ms 368888 KB Output is correct
8 Correct 452 ms 368896 KB Output is correct
9 Correct 371 ms 353212 KB Output is correct
10 Correct 406 ms 368964 KB Output is correct
11 Correct 1426 ms 369080 KB Output is correct
12 Correct 2614 ms 369124 KB Output is correct
13 Correct 1045 ms 370324 KB Output is correct
14 Correct 1115 ms 375208 KB Output is correct
15 Correct 720 ms 374148 KB Output is correct
16 Correct 719 ms 374032 KB Output is correct
17 Correct 467 ms 369412 KB Output is correct
18 Correct 465 ms 369320 KB Output is correct