oj.uz

Submission #800306

# Submission time Handle Problem Language Result Execution time Memory
800306 2023-08-01T13:17:02 Z erray Teams (IOI15_teams) C++17
77 / 100
 4000 ms 331640 KB 
#include "teams.h"

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi15_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

namespace PST {
  struct node {
    node* l = NULL;
    node* r = NULL;
    int sum = 0;
  };
  node* modify(node* prev, int l, int r, int p) {
    debug(l, r);
    node* v = new node();
    if (prev != NULL) {
      v->l = prev->l;
      v->r = prev->r;
      v->sum = prev->sum;
    }
    v->sum += 1;
    if (l < r) {
      int mid = (l + r) >> 1;
      if (p <= mid) {
        v->l = modify(v->l, l, mid, p);
      } else {
        v->r = modify(v->r, mid + 1, r, p);
      }
    }
    return v;
  }
  int get(node* v, int l, int r, int ll) {
    if (v == NULL) {
      return 0;
    }
    if (l >= ll) {
      return v->sum;
    }
    int mid = (l + r) >> 1;
    int res = 0;
    if (ll <= mid) {
      res += get(v->l, l, mid, ll);
    } 
    res += get(v->r, mid + 1, r, ll);
    return res;
  }
}

struct SegTree {
  int n;
  vector<PST::node*> roots;
  SegTree(int _n) : n(_n) {
    roots.resize(1);
    roots[0] = new PST::node();
  }
  SegTree() { } 
  PST::node* modify(int x) {
     roots.push_back(PST::modify(roots.back(), 0, n - 1, x));
     return roots.back();
  }
  int get(PST::node* v, int ll) {
    return PST::get(v, 0, n - 1, ll);
  }
};

int N;
vector<array<int, 2>> A;
SegTree st;
vector<PST::node*> vers;
vector<int> pt;
void init(int __N, int __A[], int __B[]) {
  
  N = __N;
  auto L = inverse_fuck(__A, N);
  auto R = inverse_fuck(__B, N);
  debug(N, L, R);
  A.resize(N);
  for (int i = 0; i < N; ++i) {
    A[i] = array<int, 2>{L[i], R[i]};
  }
  sort(A.begin(), A.end());
  debug(A);
  st = SegTree(N + 1);
  for (int i = 0; i < N; ++i) {
    debug(i);
    auto v = st.modify(A[i][1]);
    if (i == N - 1|| A[i + 1][0] != A[i][0]) {
      pt.push_back(A[i][0]);
      vers.push_back(v);
    }
  }
}

int can(int M, int __K[]) {
  auto K = inverse_fuck(__K, M);
  sort(K.begin(), K.end());
  if (accumulate(K.begin(), K.end(), 0LL) > N) {
    return false;
  }
  debug(M, K);
  vector<array<int, 2>> comp;
  for (int i = 0; i < M; ++i) {
    if (i == 0 || comp.back()[0] != K[i]) {
      comp.push_back({K[i], 0}); //overflow on sums
    } 
    comp.back()[1] += K[i];
  }
  auto Contains = [&](int l, int r) {
    return (l == -1 ? 0 : st.get(vers[l], r));
  };
  int s = int(comp.size());
  vector<int> from(s);
  int p = -1;
  for (int i = 0; i < s; ++i) {
    while (p + 1 < int(pt.size()) && pt[p + 1] <= comp[i][0]) {
      ++p;
    }
    from[i] = p;
  }
  debug(comp, from);
  vector<int> dp(s);
  for (int i = 0; i < s; ++i) {
    auto[x, sz] = comp[i];
    dp[i] = 0;
    for (int j = 0; j < i; ++j) {
      dp[i] = min(dp[i], dp[j] - Contains(from[j], x));
    }
    dp[i] += Contains(from[i], x) - sz;
    if (dp[i] < 0) {
      return false;
    }
  }
	return true;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 59368 KB Output is correct
2 Correct 84 ms 59444 KB Output is correct
3 Correct 79 ms 59468 KB Output is correct
4 Correct 81 ms 59432 KB Output is correct
5 Correct 65 ms 58752 KB Output is correct
6 Correct 65 ms 58816 KB Output is correct
7 Correct 63 ms 58720 KB Output is correct
8 Correct 62 ms 58892 KB Output is correct
9 Correct 70 ms 56676 KB Output is correct
10 Correct 58 ms 60236 KB Output is correct
11 Correct 60 ms 60356 KB Output is correct
12 Correct 64 ms 60392 KB Output is correct
13 Correct 68 ms 60680 KB Output is correct
14 Correct 66 ms 58624 KB Output is correct
15 Correct 77 ms 60452 KB Output is correct
16 Correct 96 ms 60500 KB Output is correct
17 Correct 64 ms 60736 KB Output is correct
18 Correct 67 ms 60740 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 59420 KB Output is correct
2 Correct 86 ms 59404 KB Output is correct
3 Correct 1503 ms 62012 KB Output is correct
4 Correct 82 ms 59456 KB Output is correct
5 Correct 567 ms 58856 KB Output is correct
6 Correct 437 ms 58808 KB Output is correct
7 Correct 68 ms 58864 KB Output is correct
8 Correct 338 ms 58848 KB Output is correct
9 Correct 57 ms 57512 KB Output is correct
10 Correct 62 ms 60328 KB Output is correct
11 Correct 71 ms 60460 KB Output is correct
12 Correct 341 ms 60656 KB Output is correct
13 Correct 190 ms 60884 KB Output is correct
14 Correct 1024 ms 62000 KB Output is correct
15 Correct 98 ms 60564 KB Output is correct
16 Correct 94 ms 60592 KB Output is correct
17 Correct 86 ms 60964 KB Output is correct
18 Correct 85 ms 60924 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 331612 KB Output is correct
2 Correct 551 ms 331612 KB Output is correct
3 Execution timed out 4056 ms 331640 KB Time limit exceeded
4 Halted 0 ms 0 KB -