oj.uz

Submission #819893

# Submission time Handle Problem Language Result Execution time Memory
819893 2023-08-10T15:04:17 Z vinisal353 Teams (IOI15_teams) C++14
100 / 100
 3007 ms 415108 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 '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 7 ms 12088 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12208 KB Output is correct
5 Correct 6 ms 12064 KB Output is correct
6 Correct 6 ms 12072 KB Output is correct
7 Correct 6 ms 12120 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 6 ms 12192 KB Output is correct
13 Correct 9 ms 12192 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 6 ms 12124 KB Output is correct
16 Correct 5 ms 12116 KB Output is correct
17 Correct 6 ms 12060 KB Output is correct
18 Correct 6 ms 12112 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 6 ms 12060 KB Output is correct
24 Correct 6 ms 12116 KB Output is correct
25 Correct 6 ms 12060 KB Output is correct
26 Correct 7 ms 12060 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 61680 KB Output is correct
2 Correct 59 ms 61636 KB Output is correct
3 Correct 58 ms 61608 KB Output is correct
4 Correct 62 ms 62196 KB Output is correct
5 Correct 35 ms 61724 KB Output is correct
6 Correct 35 ms 61792 KB Output is correct
7 Correct 33 ms 61780 KB Output is correct
8 Correct 37 ms 61684 KB Output is correct
9 Correct 35 ms 62468 KB Output is correct
10 Correct 32 ms 62080 KB Output is correct
11 Correct 33 ms 62128 KB Output is correct
12 Correct 34 ms 62112 KB Output is correct
13 Correct 41 ms 62012 KB Output is correct
14 Correct 43 ms 62232 KB Output is correct
15 Correct 52 ms 61644 KB Output is correct
16 Correct 53 ms 61728 KB Output is correct
17 Correct 42 ms 62664 KB Output is correct
18 Correct 38 ms 62536 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 64324 KB Output is correct
2 Correct 68 ms 64604 KB Output is correct
3 Correct 451 ms 124796 KB Output is correct
4 Correct 59 ms 62268 KB Output is correct
5 Correct 156 ms 65124 KB Output is correct
6 Correct 142 ms 65356 KB Output is correct
7 Correct 47 ms 64460 KB Output is correct
8 Correct 118 ms 65224 KB Output is correct
9 Correct 37 ms 62432 KB Output is correct
10 Correct 35 ms 62540 KB Output is correct
11 Correct 41 ms 62916 KB Output is correct
12 Correct 161 ms 65224 KB Output is correct
13 Correct 303 ms 68340 KB Output is correct
14 Correct 670 ms 99980 KB Output is correct
15 Correct 178 ms 68004 KB Output is correct
16 Correct 173 ms 68004 KB Output is correct
17 Correct 151 ms 66108 KB Output is correct
18 Correct 125 ms 65968 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 292260 KB Output is correct
2 Correct 475 ms 293088 KB Output is correct
3 Correct 2007 ms 415108 KB Output is correct
4 Correct 441 ms 288704 KB Output is correct
5 Correct 511 ms 293260 KB Output is correct
6 Correct 435 ms 293680 KB Output is correct
7 Correct 160 ms 291708 KB Output is correct
8 Correct 368 ms 293292 KB Output is correct
9 Correct 144 ms 287612 KB Output is correct
10 Correct 141 ms 285988 KB Output is correct
11 Correct 221 ms 287540 KB Output is correct
12 Correct 517 ms 291956 KB Output is correct
13 Correct 1368 ms 300016 KB Output is correct
14 Correct 3007 ms 365152 KB Output is correct
15 Correct 639 ms 299516 KB Output is correct
16 Correct 654 ms 300104 KB Output is correct
17 Correct 440 ms 296100 KB Output is correct
18 Correct 451 ms 295628 KB Output is correct