oj.uz

Submission #766942

# Submission time Handle Problem Language Result Execution time Memory
766942 2023-06-26T09:16:38 Z marvinthang Teams (IOI15_teams) C++17
100 / 100
 3427 ms 384848 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; }

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:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'Node* update(Node*, int, int, int, int)':
teams.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int get_sum(Node*, int, int, int, int)':
teams.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In lambda function:
teams.cpp:114:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |    int m = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:120: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)
      |                                                     ~~~
......
  120 |  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)
      |                                                      ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 77004 KB Output is correct
2 Correct 124 ms 77084 KB Output is correct
3 Correct 117 ms 76980 KB Output is correct
4 Correct 117 ms 77444 KB Output is correct
5 Correct 62 ms 75856 KB Output is correct
6 Correct 63 ms 75812 KB Output is correct
7 Correct 61 ms 75888 KB Output is correct
8 Correct 61 ms 75832 KB Output is correct
9 Correct 62 ms 76740 KB Output is correct
10 Correct 70 ms 76692 KB Output is correct
11 Correct 67 ms 76652 KB Output is correct
12 Correct 68 ms 76596 KB Output is correct
13 Correct 84 ms 76208 KB Output is correct
14 Correct 92 ms 76868 KB Output is correct
15 Correct 119 ms 76960 KB Output is correct
16 Correct 121 ms 76924 KB Output is correct
17 Correct 67 ms 76740 KB Output is correct
18 Correct 82 ms 76624 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 77424 KB Output is correct
2 Correct 165 ms 77480 KB Output is correct
3 Correct 491 ms 80728 KB Output is correct
4 Correct 141 ms 77428 KB Output is correct
5 Correct 293 ms 76188 KB Output is correct
6 Correct 288 ms 76228 KB Output is correct
7 Correct 80 ms 76224 KB Output is correct
8 Correct 214 ms 76208 KB Output is correct
9 Correct 80 ms 76696 KB Output is correct
10 Correct 63 ms 77032 KB Output is correct
11 Correct 67 ms 76940 KB Output is correct
12 Correct 198 ms 76952 KB Output is correct
13 Correct 380 ms 76672 KB Output is correct
14 Correct 887 ms 81036 KB Output is correct
15 Correct 233 ms 78884 KB Output is correct
16 Correct 225 ms 78924 KB Output is correct
17 Correct 235 ms 78608 KB Output is correct
18 Correct 163 ms 78660 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 373276 KB Output is correct
2 Correct 856 ms 373276 KB Output is correct
3 Correct 2447 ms 381096 KB Output is correct
4 Correct 796 ms 373244 KB Output is correct
5 Correct 975 ms 367188 KB Output is correct
6 Correct 829 ms 367048 KB Output is correct
7 Correct 326 ms 366940 KB Output is correct
8 Correct 708 ms 366996 KB Output is correct
9 Correct 302 ms 366880 KB Output is correct
10 Correct 296 ms 367040 KB Output is correct
11 Correct 389 ms 367124 KB Output is correct
12 Correct 692 ms 367020 KB Output is correct
13 Correct 1661 ms 367620 KB Output is correct
14 Correct 3427 ms 384848 KB Output is correct
15 Correct 987 ms 379288 KB Output is correct
16 Correct 1037 ms 379260 KB Output is correct
17 Correct 700 ms 374052 KB Output is correct
18 Correct 676 ms 374120 KB Output is correct