Submission #819895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
819895	2023-08-10T15:07:42 Z	vinisal353	Teams (IOI15_teams)	C++14	100 / 100	3607 ms	406808 KB

teams

/*************************************
*    author: marvinthang             *
*    created: 06.03.2023 21:08:07    *
*************************************/
 
#include "teams.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif
 
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }
 
static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}
 
struct Node {
	Node *lc, *rc;
	int sum;
	Node(int v = 0): lc(nullptr), rc(nullptr), sum(v) {}
	Node(Node *l, Node *r): lc(l), rc(r), sum(0) {
		if (l != nullptr) sum += l->sum;
		if (r != nullptr) sum += r->sum;
	}
};
 
Node *build(int l, int r) {
	if (l == r) return new Node();
	int m = l + r >> 1;
	return new Node(build(l, m), build(m + 1, r));
}
 
Node *update(Node *cur, int l, int r, int p, int v) {
	if (l == r) return new Node(cur->sum + v);
	int m = l + r >> 1;
	if (p <= m) return new Node(update(cur->lc, l, m, p, v), cur->rc);
	return new Node(cur->lc, update(cur->rc, m + 1, r, p, v));
}
 
int get_sum(Node *cur, int l, int r, int u, int v) {
	if (l > v || r < u) return 0;
	if (u <= l && r <= v) return cur->sum;
	int m = l + r >> 1;
	return get_sum(cur->lc, l, m, u, v) + get_sum(cur->rc, m + 1, r, u, v);
}
 
// end of template
 
const int MAX = 5e5 + 5;
 
int N, pref[MAX];
vector <int> rightAt[MAX];
Node *versions[MAX];
 
void init(int n, int A[], int B[]) {
	N = n;
	REP(i, N) rightAt[B[i]].push_back(A[i]);
	versions[N + 1] = build(1, N);
	FORDE(r, N, 1) {
		versions[r] = versions[r + 1];
		for (int l: rightAt[r]) versions[r] = update(versions[r], 1, N, l, 1);
	}
}
 
int cnt[MAX], dp[MAX];
 
int can(int M, int K[]) {
	long long sum = 0;
	REP(i, M) sum += K[i];
	if (sum > N) return 0;
	REP(i, M) ++cnt[K[i]];
 
	vector <pair <int, int>> v;
	REP(i, M) if (cnt[K[i]]) {
		v.push_back(make_pair(K[i], K[i] * cnt[K[i]]));
		cnt[K[i]] = 0;
	}
	v.emplace_back(0, 0);
	sort(ALL(v));
	stack <pair <int, int>> st;
	st.emplace(0, N + 2);
	auto getTime = [&] (int i, int j) {
		int l = v[j].fi + 1, r = N;
		while (l <= r) {
			int m = l + r >> 1;
			if (get_sum(versions[m], 1, N, v[i].fi + 1, v[j].fi) < dp[j] - dp[i]) r = m - 1;
			else l = m + 1;
		}
		return l;
	};
	FOR(i, 1, v.size()) {
		while (st.top().se <= v[i].fi) st.pop();
		dp[i] = dp[st.top().fi] + get_sum(versions[v[i].fi], 1, N, v[st.top().fi].fi + 1, v[i].fi) - v[i].se;
		if (dp[i] < 0) return 0;
		int t = getTime(st.top().fi, i);
		while (st.top().se < t) {
			st.pop();
			t = getTime(st.top().fi, i);
		}
		st.emplace(i, t);
	}
	return 1;
}

Compilation message

teams.cpp: In function 'std::ostream& print_tuple_utils(std::ostream&, const T&)':
teams.cpp:41:91: warning: 'if constexpr' only available with '-std=c++17' or '-std=gnu++17'
   41 | template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
      |                                                                                           ^~~~~~~~~
teams.cpp: In function 'Node* build(int, int)':
teams.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'Node* update(Node*, int, int, int, int)':
teams.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int get_sum(Node*, int, int, int, int)':
teams.cpp:80:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In lambda function:
teams.cpp:122:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |    int m = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:128:18: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                     ~~~
......
  128 |  FOR(i, 1, v.size()) {
teams.cpp:22:54: note: in definition of macro 'FOR'
   22 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                      ^
teams.cpp: At global scope:
teams.cpp:52:6: warning: the program should also define 'void operator delete(void*, std::size_t)' [-Wsized-deallocation]
   52 | void operator delete(void*) {}
      |      ^~~~~~~~

Subtask #1

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	11988 KB	Output is correct
2	Correct	6 ms	12040 KB	Output is correct
3	Correct	6 ms	12116 KB	Output is correct
4	Correct	6 ms	12116 KB	Output is correct
5	Correct	5 ms	12076 KB	Output is correct
6	Correct	6 ms	12148 KB	Output is correct
7	Correct	6 ms	12116 KB	Output is correct
8	Correct	6 ms	12116 KB	Output is correct
9	Correct	7 ms	12116 KB	Output is correct
10	Correct	7 ms	12200 KB	Output is correct
11	Correct	7 ms	12116 KB	Output is correct
12	Correct	6 ms	12116 KB	Output is correct
13	Correct	6 ms	12208 KB	Output is correct
14	Correct	6 ms	12116 KB	Output is correct
15	Correct	6 ms	12116 KB	Output is correct
16	Correct	5 ms	12116 KB	Output is correct
17	Correct	6 ms	12156 KB	Output is correct
18	Correct	6 ms	12116 KB	Output is correct
19	Correct	6 ms	12116 KB	Output is correct
20	Correct	6 ms	12116 KB	Output is correct
21	Correct	6 ms	12116 KB	Output is correct
22	Correct	6 ms	12116 KB	Output is correct
23	Correct	7 ms	12116 KB	Output is correct
24	Correct	6 ms	12116 KB	Output is correct
25	Correct	6 ms	12116 KB	Output is correct
26	Correct	6 ms	12116 KB	Output is correct

Subtask #2

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	60512 KB	Output is correct
2	Correct	68 ms	60468 KB	Output is correct
3	Correct	60 ms	60468 KB	Output is correct
4	Correct	63 ms	60876 KB	Output is correct
5	Correct	35 ms	61004 KB	Output is correct
6	Correct	33 ms	60924 KB	Output is correct
7	Correct	33 ms	60960 KB	Output is correct
8	Correct	33 ms	60900 KB	Output is correct
9	Correct	34 ms	61652 KB	Output is correct
10	Correct	38 ms	61576 KB	Output is correct
11	Correct	33 ms	61424 KB	Output is correct
12	Correct	38 ms	61544 KB	Output is correct
13	Correct	49 ms	61068 KB	Output is correct
14	Correct	42 ms	61260 KB	Output is correct
15	Correct	52 ms	60588 KB	Output is correct
16	Correct	54 ms	60552 KB	Output is correct
17	Correct	36 ms	61472 KB	Output is correct
18	Correct	37 ms	61416 KB	Output is correct

Subtask #3

43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	62844 KB	Output is correct
2	Correct	78 ms	63192 KB	Output is correct
3	Correct	408 ms	122916 KB	Output is correct
4	Correct	68 ms	60900 KB	Output is correct
5	Correct	166 ms	64076 KB	Output is correct
6	Correct	144 ms	64236 KB	Output is correct
7	Correct	42 ms	63356 KB	Output is correct
8	Correct	115 ms	64032 KB	Output is correct
9	Correct	34 ms	61568 KB	Output is correct
10	Correct	34 ms	61920 KB	Output is correct
11	Correct	47 ms	62048 KB	Output is correct
12	Correct	264 ms	64092 KB	Output is correct
13	Correct	413 ms	66936 KB	Output is correct
14	Correct	834 ms	98172 KB	Output is correct
15	Correct	226 ms	66508 KB	Output is correct
16	Correct	237 ms	66488 KB	Output is correct
17	Correct	164 ms	64696 KB	Output is correct
18	Correct	154 ms	64548 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	459 ms	284948 KB	Output is correct
2	Correct	453 ms	285484 KB	Output is correct
3	Correct	2110 ms	406808 KB	Output is correct
4	Correct	441 ms	281648 KB	Output is correct
5	Correct	464 ms	288580 KB	Output is correct
6	Correct	422 ms	289004 KB	Output is correct
7	Correct	172 ms	287096 KB	Output is correct
8	Correct	369 ms	288544 KB	Output is correct
9	Correct	153 ms	282840 KB	Output is correct
10	Correct	149 ms	282952 KB	Output is correct
11	Correct	296 ms	283808 KB	Output is correct
12	Correct	840 ms	287488 KB	Output is correct
13	Correct	1848 ms	293820 KB	Output is correct
14	Correct	3607 ms	357384 KB	Output is correct
15	Correct	760 ms	292388 KB	Output is correct
16	Correct	779 ms	292920 KB	Output is correct
17	Correct	539 ms	289356 KB	Output is correct
18	Correct	485 ms	288980 KB	Output is correct