제출 #386647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386647		Keshi	팀들 (IOI15_teams)	C++17	100 / 100	1471 ms	195168 KiB

teams

//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;
}*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23