oj.uz

Submission #289590

# Submission time Handle Problem Language Result Execution time Memory
289590 2020-09-02T18:44:54 Z _7_7_ Teams (IOI15_teams) C++14
100 / 100
 3943 ms 387680 KB 
#include "teams.h"
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 5e5 + 12;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, block = 850;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;
 
int n;
 
 
struct node {
	node *l, *r;
	int sum;
	node () {
		l = r = NULL;
		sum = 0;
	}
 
	node (int x) {
		sum = x;
		l = r = NULL;
	}
 
	node (node *L, node *R) {
		l = L, r = R;
		sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
	}
};
 
typedef node * pnode;
pnode root[N];
 
pnode build (int tl = 0, int tr = n - 1) {
	if (tl == tr)
		return new node();
 
	int tm = (tl + tr) >> 1;
	return new node(build(tl, tm), build(tm + 1, tr));
}
 
pnode update (pnode t, int pos, int x, int tl = 1, int tr = n) {
	if (tl == tr)
		return new node(t->sum + x);
 
	int tm = (tl + tr) >> 1;
 
	if (pos <= tm)
	    return new node(update(t->l, pos, x, tl, tm), t->r);
	return new node(t->l, update(t->r, pos, x, tm + 1, tr));		
}
 
int get (pnode t, int l, int r, int tl = 1, int tr = n) {
	if (l > r || l > tr || tl > r)
		return 0;
 
	if (l <= tl && tr <= r)
		return t->sum;
 
	int tm = (tl + tr) >> 1;
	return get(t->l, l, r, tl, tm) + get(t->r, l, r, tm + 1, tr);
}
 
 
vi g[N];
bool was[N];
int cnt[1000], pos[N];
vpii c;
 
      	
              
void init(int _n, int a[], int b[]) {
	n = _n;
	for (int i = 0; i < n; ++i)  {
		g[a[i]].pb(b[i]);          
		was[a[i]] = 1; 
		c.pb(mp(a[i], b[i]));
	}
		
	root[0] = build();
	int j = 1;
	sort(all(c));
	for (int i = 0; i < sz(c); ++i) {
		pos[c[i].f] = i + 1;
		root[i + 1] = update(root[i], c[i].s, 1);
	}

	for (int i = 1; i <= n; ++i)
		if (!pos[i])
			pos[i] = pos[i - 1];
}
 
int can(int m, int k[]) {
	int sum = 0;
	
	vpii vv;
	vi vals;
 
	for (int i = 0; i < m; ++i) {
		sum += k[i];
		if (sum > n)
			return 0;
		vals.pb(k[i]);
	}
 
	sort(all(vals));
	for (int i = 0; i < sz(vals); ) {
		int j = i, s = 0;
		while (j < sz(vals) && vals[i] == vals[j]) 
			s += vals[j++];
 
		vv.pb(mp(vals[i], s));		
		i = j;
	}
 
/*		
	if (m > block) {
		priority_queue < int, vi, greater < int > > q;
		int j = 0;
		for (auto x : vv) {
			while (j <= x.f) {
				for (auto b : g[j])
					if (b >= x.f)
						q.push(b);	
				++j;
			}
			
			while (sz(q) && x.s) {
				if (q.top() >= x.f)
					--x.s;
				q.pop();			
			}
 
			if (x.s)
				return 0;
		}
		return 1;
	}*/
 
 
	for (int i = 0; i < sz(vv); ++i)
		cnt[i] = 0;

	for (int i = 0; i < sz(vv); ++i) {
		int rest = vv[i].s;
		for (int j = i; j < sz(vv); ++j) {
			int cur = get(root[pos[vv[i].f]], vv[j].f, (j == sz(vv) - 1 ? n : vv[j + 1].f - 1)) - cnt[j];
//			cerr << i << ' ' << cur << ' ' << vv[j].f << ' ' << (j == sz(vv) - 1 ? n : vv[j + 1].f - 1) << ' ' << cnt[j] << endl;
			cnt[j] += min(cur, rest);
			rest -= min(cur, rest);
			if (!rest)
				break;
		}
 
		if (rest)
			return 0;
	}
		
 
	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:117:6: warning: unused variable 'j' [-Wunused-variable]
  117 |  int j = 1;
      |      ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 78360 KB Output is correct
2 Correct 187 ms 78420 KB Output is correct
3 Correct 180 ms 78316 KB Output is correct
4 Correct 188 ms 79596 KB Output is correct
5 Correct 106 ms 77164 KB Output is correct
6 Correct 108 ms 77036 KB Output is correct
7 Correct 107 ms 77036 KB Output is correct
8 Correct 109 ms 77036 KB Output is correct
9 Correct 104 ms 75240 KB Output is correct
10 Correct 100 ms 74988 KB Output is correct
11 Correct 98 ms 77932 KB Output is correct
12 Correct 99 ms 74988 KB Output is correct
13 Correct 119 ms 77932 KB Output is correct
14 Correct 121 ms 76140 KB Output is correct
15 Correct 167 ms 78148 KB Output is correct
16 Correct 168 ms 78188 KB Output is correct
17 Correct 123 ms 78008 KB Output is correct
18 Correct 110 ms 78060 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 78828 KB Output is correct
2 Correct 237 ms 78828 KB Output is correct
3 Correct 306 ms 81900 KB Output is correct
4 Correct 183 ms 79596 KB Output is correct
5 Correct 128 ms 77424 KB Output is correct
6 Correct 130 ms 77420 KB Output is correct
7 Correct 127 ms 77420 KB Output is correct
8 Correct 130 ms 77548 KB Output is correct
9 Correct 94 ms 75244 KB Output is correct
10 Correct 96 ms 75244 KB Output is correct
11 Correct 136 ms 78316 KB Output is correct
12 Correct 1221 ms 75412 KB Output is correct
13 Correct 362 ms 78468 KB Output is correct
14 Correct 339 ms 79852 KB Output is correct
15 Correct 198 ms 78700 KB Output is correct
16 Correct 199 ms 78704 KB Output is correct
17 Correct 134 ms 78572 KB Output is correct
18 Correct 132 ms 78444 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1347 ms 379756 KB Output is correct
2 Correct 1322 ms 379784 KB Output is correct
3 Correct 1563 ms 385760 KB Output is correct
4 Correct 1217 ms 381536 KB Output is correct
5 Correct 612 ms 372960 KB Output is correct
6 Correct 613 ms 372832 KB Output is correct
7 Correct 595 ms 372960 KB Output is correct
8 Correct 610 ms 372960 KB Output is correct
9 Correct 478 ms 358884 KB Output is correct
10 Correct 503 ms 373088 KB Output is correct
11 Correct 2275 ms 373148 KB Output is correct
12 Correct 3943 ms 373336 KB Output is correct
13 Correct 1529 ms 380884 KB Output is correct
14 Correct 1593 ms 387680 KB Output is correct
15 Correct 1064 ms 385888 KB Output is correct
16 Correct 1053 ms 385760 KB Output is correct
17 Correct 610 ms 380768 KB Output is correct
18 Correct 612 ms 381024 KB Output is correct