Submission #970702

#	Time	Username	Problem	Language	Result	Execution time	Memory
970702		hqminhuwu	Teams (IOI15_teams)	C++14	0 / 100	553 ms	188760 KiB

teams

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <pii, int> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7; // 998244353;

struct node {
	pii val;
	int l, r;
	node () : val({oo, oo}), l(0), r(0){}
};

node tree[20 * N];
int cnt, n;
piii d[N], e[N];

int update (int pre, int l, int r, int pos){
	if (l == r){
		tree[++cnt].val = {e[l].nd, l};
		return cnt;
	}

	int mid = (l + r) >> 1;
	int i = ++cnt;
	tree[i] = tree[pre];

	if (pos <= mid)
		tree[i].l = update(tree[pre].l, l, mid, pos);	
	else tree[i].r = update(tree[pre].r, mid + 1, r, pos);

	tree[i].val = min (tree[tree[i].l].val, tree[tree[i].r].val);
	return i;
}

pii get (int i, int l, int r, int u, int v){
	if (r < u || l > v) return {oo, oo};
	
	if (l >= u && r <= v)
		return tree[i].val;

	int mid = (l + r) >> 1;

	return min(get(tree[i].l, l, mid, u, v), get(tree[i].r, mid + 1, r, u, v));
}

void mdf (int i, int l, int r, int pos, pii val){
	if (l == r){
		tree[i].val = val;
		return;
	}
	
	int mid = (l + r) >> 1;
	if (pos <= mid)
		mdf(tree[i].l, l, mid, pos, val);
	else mdf(tree[i].r, mid + 1, r, pos, val);
	tree[i].val = min (tree[tree[i].l].val, tree[tree[i].r].val);
}

vector <int> z, y;
int pos[N], root[N];

void init (int num, int a[], int b[]){
	n = num;
	
	forr (i, 1, n){
		d[i] = {{a[i - 1], b[i - 1]}, i};
		e[i] = {{b[i - 1], a[i - 1]}, i};
		z.pb(a[i - 1]);
		y.pb(b[i - 1]);
	}

	sort(d + 1, d + 1 + n);
	sort(e + 1, e + 1 + n);	
	z.pb(0);
	y.pb(0);
	sort(all(z));
	sort(all(y));

	forr (i, 1, n){
		pos[e[i].nd] = i;
		//cout << d[i].st.st << " " << d[i].st.nd << " " << d[i].nd << "\n";
	}

	// for (int u : z){
	// 	cout << u << " ";
	// }
	// cout << "\n";
	
	forr (i, 1, n){
		root[i] = update(root[i - 1], 1, n, pos[i]);
	}

	z.pb(oo);

}

int can (int m, int k[]){
	sort(k, k + m);
	vector <piii> q;

	int flag = 1;
	forf (i, 0, m){
		if (k[i] < z[1] || k[i] > y.back()){
			flag = 0;
			break;
		}
	
		int u = upper_bound(all(z), k[i]) - z.begin() - 1;
		int v = lower_bound(all(y), k[i]) - y.begin();
		pii tmp = get(root[u], 1, n, v, n);
		if (tmp.st > n)
			flag = 0;
		else {
			q.pb({tmp, root[u]});
			mdf(root[u], 1, n, tmp.nd, {oo, oo});
		}	
	}

	for (piii t : q){
		mdf(t.nd, 1, n, t.st.nd, t.st);
	}

	return flag;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:127:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  127 |   int u = upper_bound(all(z), k[i]) - z.begin() - 1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:128:37: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  128 |   int v = lower_bound(all(y), k[i]) - y.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23