oj.uz

Submission #120456

# Submission time Handle Problem Language Result Execution time Memory
120456 2019-06-24T14:26:48 Z RockyB Teams (IOI15_teams) C++11
77 / 100
 4000 ms 162956 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include "teams.h"
#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

const int MAXN = (int)5e5 + 7;

typedef long long ll;

using namespace std;

int N;
vector < pair <int, int > > a;

int sz;
int root[MAXN];
vector <int> q[MAXN];

ll dp[MAXN];

struct tree {
	int t[MAXN * 30], ls[MAXN * 30], rs[MAXN * 30];
	inline void upd(int p, int &v, int lv, int tl = 1, int tr = MAXN) {
		v = ++sz;
		if (tl == tr) {
			t[v] = t[lv] + 1;
			return;
		}
		int tm = tl + tr >> 1;
		if (p <= tm) rs[v] = rs[lv], upd(p, ls[v], ls[lv], tl, tm);
		else ls[v] = ls[lv], upd(p, rs[v], rs[lv], tm + 1, tr);
		t[v] = t[ls[v]] + t[rs[v]];
	}
	inline int get(int l, int r, int v, int tl = 1, int tr = MAXN) {
		//cerr << tl << ' ' << tr << ' ' << v << endl;
		if (tl > r || tr < l || !v) return 0;
		if (l <= tl && tr <= r) return t[v];
		int tm = tl + tr >> 1;
		return get(l, r, ls[v], tl, tm) + get(l, r, rs[v], tm + 1, tr);
	}
} t;

void init(int _N, int A[], int B[]) {
	N = _N;
	for (int i = 0; i < N; i++) {
		a.pb({A[i], B[i]});
		q[A[i]].pb(B[i]);
	}
	root[0] = ++sz;
	for (int i = 1; i < MAXN; i++) {
		root[i] = root[i - 1];
		for (auto it : q[i]) {
			t.upd(it, root[i], root[i]);
		}
	}
}
int can(int M, int K[]) {
	sort (K, K + M);	
	ll sum = 0;
	vector < pair <int, int> > k;
	for (int i = 0; i < M; i++) {
		if (!sz(k) || k.back().f != K[i]) k.pb({K[i], 1});
		else k.back().s++;
		sum += K[i];
	}
	if (sum > sz(a)) return 0;
	for (int i = 0; i < sz(k); i++) { 
		int cnt = t.get(k[i].f, MAXN, root[k[i].f]);
		ll cur = (ll)k[i].f * k[i].s;
		if (cnt < cur) return 0;
		dp[i] = 0;
		for (int j = i - 1; j >= 0; j--) {
			int com = t.get(k[i].f, MAXN, root[k[j].f]);
			dp[i] = max(dp[i], dp[j] + com);
		}
		dp[i] += cur - cnt;
		if (dp[i] > 0) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In member function 'void tree::upd(int, int&, int, int, int)':
teams.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
            ~~~^~~~
teams.cpp: In member function 'int tree::get(int, int, int, int, int)':
teams.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
            ~~~^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14052 KB Output is correct
2 Correct 15 ms 14080 KB Output is correct
3 Correct 16 ms 14080 KB Output is correct
4 Correct 16 ms 14080 KB Output is correct
5 Correct 15 ms 14080 KB Output is correct
6 Correct 18 ms 14080 KB Output is correct
7 Correct 17 ms 14080 KB Output is correct
8 Correct 16 ms 14080 KB Output is correct
9 Correct 16 ms 14080 KB Output is correct
10 Correct 17 ms 14080 KB Output is correct
11 Correct 16 ms 14080 KB Output is correct
12 Correct 17 ms 14080 KB Output is correct
13 Correct 16 ms 14080 KB Output is correct
14 Correct 15 ms 14052 KB Output is correct
15 Correct 18 ms 14080 KB Output is correct
16 Correct 15 ms 14080 KB Output is correct
17 Correct 15 ms 14080 KB Output is correct
18 Correct 17 ms 14080 KB Output is correct
19 Correct 15 ms 13980 KB Output is correct
20 Correct 16 ms 14080 KB Output is correct
21 Correct 15 ms 14080 KB Output is correct
22 Correct 16 ms 14080 KB Output is correct
23 Correct 35 ms 14080 KB Output is correct
24 Correct 16 ms 14080 KB Output is correct
25 Correct 15 ms 14080 KB Output is correct
26 Correct 15 ms 14080 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 40880 KB Output is correct
2 Correct 105 ms 42052 KB Output is correct
3 Correct 101 ms 41936 KB Output is correct
4 Correct 111 ms 42600 KB Output is correct
5 Correct 53 ms 40556 KB Output is correct
6 Correct 49 ms 40428 KB Output is correct
7 Correct 49 ms 40428 KB Output is correct
8 Correct 46 ms 40432 KB Output is correct
9 Correct 49 ms 40940 KB Output is correct
10 Correct 46 ms 40576 KB Output is correct
11 Correct 47 ms 40580 KB Output is correct
12 Correct 46 ms 40684 KB Output is correct
13 Correct 55 ms 40940 KB Output is correct
14 Correct 63 ms 41452 KB Output is correct
15 Correct 88 ms 41964 KB Output is correct
16 Correct 87 ms 41836 KB Output is correct
17 Correct 48 ms 40812 KB Output is correct
18 Correct 49 ms 40812 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 41404 KB Output is correct
2 Correct 105 ms 42704 KB Output is correct
3 Correct 214 ms 46112 KB Output is correct
4 Correct 101 ms 42604 KB Output is correct
5 Correct 1357 ms 41384 KB Output is correct
6 Correct 1018 ms 41324 KB Output is correct
7 Correct 56 ms 41196 KB Output is correct
8 Correct 782 ms 41232 KB Output is correct
9 Correct 50 ms 40812 KB Output is correct
10 Correct 52 ms 40812 KB Output is correct
11 Correct 127 ms 40940 KB Output is correct
12 Correct 752 ms 41196 KB Output is correct
13 Correct 285 ms 41964 KB Output is correct
14 Correct 209 ms 44268 KB Output is correct
15 Correct 128 ms 42740 KB Output is correct
16 Correct 121 ms 42700 KB Output is correct
17 Correct 89 ms 41612 KB Output is correct
18 Correct 81 ms 41452 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 149460 KB Output is correct
2 Correct 830 ms 156240 KB Output is correct
3 Correct 1034 ms 162956 KB Output is correct
4 Correct 705 ms 155956 KB Output is correct
5 Execution timed out 4093 ms 146996 KB Time limit exceeded
6 Halted 0 ms 0 KB -