oj.uz

Submission #766944

# Submission time Handle Problem Language Result Execution time Memory
766944 2023-06-26T09:17:08 Z marvinthang Teams (IOI15_teams) C++17
100 / 100
 3187 ms 406924 KB 
/*************************************
*    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;
		while (dp[i] < dp[st.top().fi]) st.pop();
		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;
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

int main() {
	_inputFile = fopen("teams.in", "rb");
	_outputFile = fopen("teams.out", "w");
    int N;
    N = _readInt();
    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) {
    	A[i] = _readInt();
    	B[i] = _readInt();
    }
    init(N, A, B);
    int Q;
    Q = _readInt();
    for (int i = 0; i < Q; ++i) {
    	int M;
    	M = _readInt();
	int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		K[j] = _readInt();
    	}
    	fprintf(_outputFile,"%d\n", can(M, K));
    }
    return 0;
}
#endif

Compilation message

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 7 ms 11988 KB Output is correct
2 Correct 5 ms 12000 KB Output is correct
3 Correct 5 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12052 KB Output is correct
7 Correct 6 ms 12096 KB Output is correct
8 Correct 5 ms 12116 KB Output is correct
9 Correct 5 ms 12116 KB Output is correct
10 Correct 6 ms 12200 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 5 ms 12116 KB Output is correct
13 Correct 5 ms 12192 KB Output is correct
14 Correct 5 ms 12116 KB Output is correct
15 Correct 5 ms 12116 KB Output is correct
16 Correct 5 ms 12116 KB Output is correct
17 Correct 5 ms 12116 KB Output is correct
18 Correct 6 ms 12040 KB Output is correct
19 Correct 5 ms 12116 KB Output is correct
20 Correct 5 ms 12116 KB Output is correct
21 Correct 7 ms 12040 KB Output is correct
22 Correct 6 ms 12116 KB Output is correct
23 Correct 6 ms 12156 KB Output is correct
24 Correct 6 ms 12116 KB Output is correct
25 Correct 5 ms 12116 KB Output is correct
26 Correct 5 ms 12116 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 60504 KB Output is correct
2 Correct 58 ms 60532 KB Output is correct
3 Correct 59 ms 60480 KB Output is correct
4 Correct 62 ms 60888 KB Output is correct
5 Correct 34 ms 60996 KB Output is correct
6 Correct 32 ms 61012 KB Output is correct
7 Correct 31 ms 61004 KB Output is correct
8 Correct 36 ms 60984 KB Output is correct
9 Correct 35 ms 61612 KB Output is correct
10 Correct 35 ms 61772 KB Output is correct
11 Correct 33 ms 61524 KB Output is correct
12 Correct 34 ms 61488 KB Output is correct
13 Correct 40 ms 61040 KB Output is correct
14 Correct 42 ms 61244 KB Output is correct
15 Correct 51 ms 60576 KB Output is correct
16 Correct 50 ms 60604 KB Output is correct
17 Correct 35 ms 61472 KB Output is correct
18 Correct 35 ms 61404 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 62884 KB Output is correct
2 Correct 63 ms 63092 KB Output is correct
3 Correct 446 ms 122836 KB Output is correct
4 Correct 57 ms 60904 KB Output is correct
5 Correct 260 ms 63236 KB Output is correct
6 Correct 232 ms 63668 KB Output is correct
7 Correct 40 ms 63300 KB Output is correct
8 Correct 183 ms 63616 KB Output is correct
9 Correct 33 ms 61652 KB Output is correct
10 Correct 33 ms 61884 KB Output is correct
11 Correct 40 ms 62020 KB Output is correct
12 Correct 187 ms 64160 KB Output is correct
13 Correct 302 ms 66952 KB Output is correct
14 Correct 693 ms 98204 KB Output is correct
15 Correct 184 ms 66544 KB Output is correct
16 Correct 172 ms 66536 KB Output is correct
17 Correct 175 ms 64656 KB Output is correct
18 Correct 129 ms 64568 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 284948 KB Output is correct
2 Correct 445 ms 285528 KB Output is correct
3 Correct 2011 ms 406924 KB Output is correct
4 Correct 427 ms 281704 KB Output is correct
5 Correct 704 ms 286924 KB Output is correct
6 Correct 669 ms 287540 KB Output is correct
7 Correct 169 ms 286992 KB Output is correct
8 Correct 556 ms 287508 KB Output is correct
9 Correct 144 ms 282856 KB Output is correct
10 Correct 145 ms 282936 KB Output is correct
11 Correct 222 ms 283808 KB Output is correct
12 Correct 529 ms 287496 KB Output is correct
13 Correct 1362 ms 293972 KB Output is correct
14 Correct 3187 ms 357268 KB Output is correct
15 Correct 695 ms 292416 KB Output is correct
16 Correct 773 ms 292800 KB Output is correct
17 Correct 482 ms 289360 KB Output is correct
18 Correct 454 ms 288936 KB Output is correct