oj.uz

Submission #608395

# Submission time Handle Problem Language Result Execution time Memory
608395 2022-07-27T07:24:51 Z cheissmart Teams (IOI15_teams) C++14
100 / 100
 1628 ms 355612 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7, N = 5e5 + 7;
 
int n;
int l[N], r[N];
vi p, rp;
 
struct node {
	node *l, *r;
	int cnt;
	node() { l = r = nullptr; cnt = 0; }
	node (node *_l, node *_r) {
		l = _l, r = _r;
		cnt = (l ? l -> cnt : 0) + (r ? r -> cnt : 0);
	}
};
 
vi ev[N];
 
node* h[N];
 
node* lc(node* t) { return t ? t -> l : nullptr; }
node* rc(node* t) { return t ? t -> r : nullptr; }
int ct(node* t) { return t ? t -> cnt : 0; }
 
node* upd(node* t, int pos, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		node* tt = new node();
		tt -> cnt = 1;
		return tt;
	}
	int tm = (tl + tr) / 2;
	if(pos < tm) return new node(upd(lc(t), pos, tl, tm), rc(t));
	else return new node(lc(t), upd(rc(t), pos, tm, tr));
}
 
int qry(node* t, int lb, int rb, int tl = 0, int tr = n) {
	if(!t) return 0;
	if(lb <= tl && tr <= rb) return t -> cnt;
	int tm = (tl + tr) / 2;
	int ans = 0;
	if(lb < tm) ans += qry(t -> l, lb, rb, tl, tm);
	if(rb > tm) ans += qry(t -> r, lb, rb, tm, tr);
	return ans;
}
 
int find_who(node* x, node* y, int cnt, int tl = 0, int tr = n) {
	assert(ct(y) - ct(x) > cnt);
	if(tr - tl == 1) return tl;
	int tm = (tl + tr) / 2;
	if(ct(lc(y)) - ct(lc(x)) > cnt)
		return find_who(lc(x), lc(y), cnt, tl, tm);
	else
		return find_who(rc(x), rc(y), cnt - (ct(lc(y)) - ct(lc(x))), tm, tr);
}
 
void init(int _n, int _l[], int _r[]) {
	n = _n;
	for(int i = 0; i < n; i++)
		l[i] = _l[i], r[i] = _r[i];
 
	p = vi(n); iota(ALL(p), 0);
	sort(ALL(p), [&] (int x, int y) {
		return r[x] < r[y];
	});
	for(int i = 0; i < n; i++)
		rp.PB(r[p[i]]);
	for(int i = 0; i < n; i++)
		ev[l[p[i]]].PB(i);
	for(int i = 1; i <= n; i++) {
		h[i] = h[i - 1];
		for(int j:ev[i])
			h[i] = upd(h[i], j);
	}
}
 
struct seg {
	int r, hi;
};
 
int can(int m, int a[]) {
	if(accumulate(a, a + m, 0LL) > n) return 0;
	sort(a, a + m);
 
	V<seg> stk;
	stk.PB({0, n});
	for(int i = 0; i < m; i++) {
		int j = lower_bound(ALL(rp), a[i]) - rp.begin();
		while(stk.back().hi < j) {
			assert(SZ(stk));
			stk.pop_back();
		}
		int need = a[i], at_least = j;
		while(need && SZ(stk)) {
			int lb = stk.back().r, rb = a[i]; // (lb, rb]
			int cnt = qry(h[rb], at_least, stk.back().hi) - qry(h[lb], at_least, stk.back().hi);
			if(cnt < need) {
				at_least = stk.back().hi;
				stk.pop_back();
				need -= cnt;
			} else if(cnt == need) {
				at_least = stk.back().hi;
				stk.pop_back();
				stk.PB({a[i], at_least});
				need -= cnt;
				break;
			} else {
				int dead = qry(h[rb], 0, at_least) - qry(h[lb], 0, at_least);
				int who = find_who(h[lb], h[rb], need + dead);
				stk.PB({a[i], who});
				break;
			}
		}
		if(stk.empty()) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:104:38: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  104 |   int j = lower_bound(ALL(rp), a[i]) - rp.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 9 ms 12108 KB Output is correct
4 Correct 9 ms 12084 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 12084 KB Output is correct
7 Correct 7 ms 12008 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 12036 KB Output is correct
14 Correct 7 ms 12020 KB Output is correct
15 Correct 8 ms 11988 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 7 ms 12024 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 7 ms 11988 KB Output is correct
21 Correct 7 ms 11984 KB Output is correct
22 Correct 8 ms 12044 KB Output is correct
23 Correct 6 ms 11988 KB Output is correct
24 Correct 7 ms 11988 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 6 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 72408 KB Output is correct
2 Correct 133 ms 72332 KB Output is correct
3 Correct 123 ms 72268 KB Output is correct
4 Correct 127 ms 72736 KB Output is correct
5 Correct 76 ms 71108 KB Output is correct
6 Correct 77 ms 71092 KB Output is correct
7 Correct 76 ms 71092 KB Output is correct
8 Correct 79 ms 71108 KB Output is correct
9 Correct 104 ms 71196 KB Output is correct
10 Correct 91 ms 70932 KB Output is correct
11 Correct 101 ms 70880 KB Output is correct
12 Correct 89 ms 71036 KB Output is correct
13 Correct 126 ms 71332 KB Output is correct
14 Correct 110 ms 71620 KB Output is correct
15 Correct 118 ms 72244 KB Output is correct
16 Correct 119 ms 72176 KB Output is correct
17 Correct 79 ms 71176 KB Output is correct
18 Correct 80 ms 70968 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 72768 KB Output is correct
2 Correct 129 ms 72704 KB Output is correct
3 Correct 287 ms 75640 KB Output is correct
4 Correct 138 ms 72680 KB Output is correct
5 Correct 125 ms 71432 KB Output is correct
6 Correct 115 ms 71488 KB Output is correct
7 Correct 82 ms 71424 KB Output is correct
8 Correct 119 ms 71460 KB Output is correct
9 Correct 116 ms 71108 KB Output is correct
10 Correct 163 ms 71340 KB Output is correct
11 Correct 193 ms 71340 KB Output is correct
12 Correct 219 ms 71296 KB Output is correct
13 Correct 373 ms 71656 KB Output is correct
14 Correct 387 ms 74052 KB Output is correct
15 Correct 216 ms 72664 KB Output is correct
16 Correct 203 ms 72776 KB Output is correct
17 Correct 135 ms 71496 KB Output is correct
18 Correct 156 ms 71620 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 349888 KB Output is correct
2 Correct 940 ms 349772 KB Output is correct
3 Correct 1444 ms 355612 KB Output is correct
4 Correct 857 ms 349900 KB Output is correct
5 Correct 520 ms 343516 KB Output is correct
6 Correct 566 ms 343424 KB Output is correct
7 Correct 434 ms 343412 KB Output is correct
8 Correct 479 ms 343484 KB Output is correct
9 Correct 510 ms 342676 KB Output is correct
10 Correct 565 ms 342728 KB Output is correct
11 Correct 681 ms 342772 KB Output is correct
12 Correct 852 ms 342856 KB Output is correct
13 Correct 1424 ms 344220 KB Output is correct
14 Correct 1628 ms 351608 KB Output is correct
15 Correct 817 ms 348440 KB Output is correct
16 Correct 830 ms 348420 KB Output is correct
17 Correct 631 ms 343264 KB Output is correct
18 Correct 548 ms 343440 KB Output is correct