Submission #417707

#	Time	Username	Problem	Language	Result	Execution time	Memory
417707		ja_kingy	Teams (IOI15_teams)	C++14	100 / 100	1032 ms	175420 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

struct node {
	int lc, rc, cnt;
} st[1<<24];

const int mxN = 5e5+1;
int n, ncnt = 1, rts[mxN];
int upd(int x, int t, int l, int r) {
	st[ncnt] = st[t];
	t = ncnt++;
	st[t].cnt++;
	if (r - l == 1) return t; 
	int m = l+r>>1;
	if (x < m) st[t].lc = upd(x, st[t].lc, l, m);
	else st[t].rc = upd(x, st[t].rc, m, r);
	return t;
}

int merge(int x, int t, int ot, int l, int r) {
	if (x <= 0) return ot;
	if (st[t].cnt - st[ot].cnt <= x) return t;
	int nt = ncnt++;
	if (r - l == 1) {
		st[nt].cnt = x + st[ot].cnt;
		return nt;
	}
	int m = l+r>>1;
	st[nt].lc = merge(x, st[t].lc, st[ot].lc, l, m);
	st[nt].rc = merge(x-st[st[t].lc].cnt+st[st[ot].lc].cnt, st[t].rc, st[ot].rc, m, r);
	st[nt].cnt = st[st[nt].lc].cnt + st[st[nt].rc].cnt;
	return nt;
}

int get_lt(int x, int t, int ot, int l, int r) {
	if (x >= r) return st[t].cnt - st[ot].cnt;
	if (x <= l) return 0;
	int m = l+r>>1;
	return get_lt(x, st[t].lc, st[ot].lc, l, m) + get_lt(x, st[t].rc, st[ot].rc, m, r);
}

void init(int N, int A[], int B[]) {
	n = N;
	vector<pii> order;
	for (int i = 0; i < N; ++i) {
		order.push_back({A[i], B[i]});
	}
	sort(order.begin(), order.end());
	int it = 0;
	for (int i = 1; i <= N; ++i) {
		rts[i] = rts[i-1];
		while (it < N && order[it].first == i) {
			rts[i] = upd(order[it].second, rts[i], 1, N+1);
			it++;
		}
	}
}

int can(int M, int K[]) {
	sort(K, K+M);
	int rt = 0, pv = 0;
	for (int i = 0; i < M; ++i) {
		int x = K[i];
		int f = get_lt(x, rts[x], rt, 1, n+1);
		rt = merge(x+f, rts[x], rt, 1, n+1);
		if (st[rt].cnt != x+f+pv) return 0;
		pv = st[rt].cnt;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int upd(int, int, int, int)':
teams.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m = l+r>>1;
      |          ~^~
teams.cpp: In function 'int merge(int, int, int, int, int)':
teams.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int m = l+r>>1;
      |          ~^~
teams.cpp: In function 'int get_lt(int, int, int, int, int)':
teams.cpp:42:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int m = l+r>>1;
      |          ~^~

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