oj.uz

답안 #386647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386647 2021-04-07T06:56:44 Z Keshi 팀들 (IOI15_teams) C++17
100 / 100
 1471 ms 195168 KB 
//In the name of God
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll maxm = 3e7;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll cnt[maxm], lc[maxm], rc[maxm];
ll root[maxn], t;
vector<ll> g[maxn];
pll c[maxn];
ll d[maxn], ee[maxn];
ll n;

ll add(ll id, ll s, ll e, ll x){
	if(x < s || e <= x) return id;
	ll nd = t++;
	if(e - s == 1){
		cnt[nd]++;
		return nd;
	}
	ll mid = (s + e) >> 1;
	lc[nd] = add(lc[id], s, mid, x);
	rc[nd] = add(rc[id], mid, e, x);
	cnt[nd] = cnt[id] + 1;
	return nd;
}

void init(int N, int A[], int B[]){
	n = N;
	root[0] = t++;
	for(ll i = 0; i < n; i++){
		g[A[i]].pb(i);
		c[i] = Mp(B[i], i);
	}
	sort(c, c + N);
	for(ll i = 0; i < n; i++){
		d[c[i].S] = i;
	}
	for(ll i = 0; i <= n; i++){
		ee[i] = lower_bound(c, c + n, Mp(i, -inf)) - c;
	}
	for(ll i = 1; i <= n; i++){
		root[i] = root[i - 1];
		for(ll j : g[i]){
			root[i] = add(root[i], 0, n, d[j]);
		}
	}
}

ll get(ll id, ll nd, ll s, ll e, ll l, ll r){
	if(r <= s || e <= l) return 0;
	if(l <= s && e <= r) return cnt[id] - cnt[nd];
	ll mid = (s + e) >> 1;
	return get(lc[id], lc[nd], s, mid, l, r) + get(rc[id], rc[nd], mid, e, l, r);
}

ll find(ll id, ll nd, ll s, ll e, ll x){
	if(cnt[id] - cnt[nd] < x) return e;
	if(e - s == 1) return s;
	ll mid = (s + e) >> 1;
	if(cnt[lc[id]] - cnt[lc[nd]] >= x) return find(lc[id], lc[nd], s, mid, x);
	x -= cnt[lc[id]] - cnt[lc[nd]];
	return find(rc[id], rc[nd], mid, e, x);
}
ll st(ll id, ll nd, ll s, ll e, ll l, ll r){
	if(r <= s || e <= l) return nd;
	if(l <= s && e <= r) return id;
	ll mid = (s + e) >> 1;
	ll dd = t++;
	lc[dd] = st(lc[id], lc[nd], s, mid, l, r);
	rc[dd] = st(rc[id], rc[nd], mid, e, l, r);
	cnt[dd] = cnt[lc[dd]] + cnt[rc[dd]];
	return dd;
}

int can(int m, int k[]){
	ll now = 0;
	sort(k, k + m);
	for(ll i = 0; i < m; i++){
		ll x = find(root[k[i]], now, 0, n, k[i] + get(root[k[i]], now, 0, n, 0, ee[k[i]]));
		if(x == n || c[x].F < k[i]) return 0;
		now = st(root[k[i]], now, 0, n, 0, x + 1);
	}
	return 1;
}

/*int main(){
	freopen("teams.in", "r", stdin);

	ll N, q, a[100], b[100], m, k[100];
	cin >> N;
	for(ll i = 0; i < N; i++){
		cin >> a[i] >> b[i];
	}
	init(N, a, b);
	cin >> q;
	for(ll i = 0; i < q; i++){
		cin >> m;
		for(ll j = 0; j < m; j++){
			cin >> k[j];
		}
		cout << "# " << can(m, k) << "\n";
	}

    return 0;
}*/

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:56:46: warning: conversion from 'long int' to 'll' {aka 'int'} may change value [-Wconversion]
   56 |   ee[i] = lower_bound(c, c + n, Mp(i, -inf)) - c;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Correct 10 ms 12140 KB Output is correct
4 Correct 9 ms 12172 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Correct 8 ms 12288 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 8 ms 12140 KB Output is correct
12 Correct 10 ms 12396 KB Output is correct
13 Correct 9 ms 12268 KB Output is correct
14 Correct 9 ms 12268 KB Output is correct
15 Correct 10 ms 12140 KB Output is correct
16 Correct 9 ms 12140 KB Output is correct
17 Correct 9 ms 12288 KB Output is correct
18 Correct 9 ms 12140 KB Output is correct
19 Correct 8 ms 12140 KB Output is correct
20 Correct 8 ms 12140 KB Output is correct
21 Correct 10 ms 12140 KB Output is correct
22 Correct 10 ms 12140 KB Output is correct
23 Correct 8 ms 12140 KB Output is correct
24 Correct 8 ms 12140 KB Output is correct
25 Correct 8 ms 12140 KB Output is correct
26 Correct 8 ms 12140 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 37356 KB Output is correct
2 Correct 113 ms 37356 KB Output is correct
3 Correct 116 ms 37384 KB Output is correct
4 Correct 111 ms 37740 KB Output is correct
5 Correct 60 ms 36388 KB Output is correct
6 Correct 63 ms 36460 KB Output is correct
7 Correct 61 ms 36332 KB Output is correct
8 Correct 59 ms 36332 KB Output is correct
9 Correct 73 ms 42340 KB Output is correct
10 Correct 61 ms 39452 KB Output is correct
11 Correct 51 ms 36452 KB Output is correct
12 Correct 55 ms 36324 KB Output is correct
13 Correct 83 ms 36328 KB Output is correct
14 Correct 83 ms 36708 KB Output is correct
15 Correct 101 ms 37356 KB Output is correct
16 Correct 101 ms 37356 KB Output is correct
17 Correct 62 ms 36204 KB Output is correct
18 Correct 65 ms 36332 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 37996 KB Output is correct
2 Correct 117 ms 37996 KB Output is correct
3 Correct 311 ms 50028 KB Output is correct
4 Correct 108 ms 39148 KB Output is correct
5 Correct 159 ms 56300 KB Output is correct
6 Correct 166 ms 53740 KB Output is correct
7 Correct 66 ms 37996 KB Output is correct
8 Correct 125 ms 49772 KB Output is correct
9 Correct 74 ms 43108 KB Output is correct
10 Correct 132 ms 55560 KB Output is correct
11 Correct 147 ms 55780 KB Output is correct
12 Correct 195 ms 56164 KB Output is correct
13 Correct 339 ms 56296 KB Output is correct
14 Correct 343 ms 53868 KB Output is correct
15 Correct 152 ms 53740 KB Output is correct
16 Correct 155 ms 53484 KB Output is correct
17 Correct 128 ms 52716 KB Output is correct
18 Correct 120 ms 52584 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 787 ms 152812 KB Output is correct
2 Correct 789 ms 152812 KB Output is correct
3 Correct 1347 ms 179772 KB Output is correct
4 Correct 784 ms 159852 KB Output is correct
5 Correct 569 ms 193388 KB Output is correct
6 Correct 585 ms 187884 KB Output is correct
7 Correct 330 ms 151660 KB Output is correct
8 Correct 569 ms 180844 KB Output is correct
9 Correct 380 ms 185692 KB Output is correct
10 Correct 471 ms 190940 KB Output is correct
11 Correct 635 ms 191584 KB Output is correct
12 Correct 816 ms 192732 KB Output is correct
13 Correct 1405 ms 195168 KB Output is correct
14 Correct 1471 ms 191972 KB Output is correct
15 Correct 759 ms 191076 KB Output is correct
16 Correct 776 ms 192552 KB Output is correct
17 Correct 469 ms 185612 KB Output is correct
18 Correct 469 ms 184528 KB Output is correct