Submission #288882

#	Time	Username	Problem	Language	Result	Execution time	Memory
288882		Berted	Teams (IOI15_teams)	C++14	0 / 100	314 ms	23928 KiB

teams

#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>

const int SZ = (1 << 20) + 5, SZ2 = 500005;

int n, seg[SZ], lazy[SZ], pref[SZ2], suf[SZ2];
using namespace std;

void build(int idx, int L, int R)
{
	if (L <= R)
	{
		if (L == R) {seg[idx] = pref[L - 1];}
		else
		{
			int M = L + R >> 1;
			build(2 * idx, L, M);
			build(2 * idx + 1, M + 1, R);
			seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

inline void prop(int idx, int L, int R)
{
	if (L <= R && lazy[idx])
	{
		seg[idx] += lazy[idx];
		if (L < R)
		{
			lazy[2 * idx] += lazy[idx];
			lazy[2 * idx + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

inline void upd(int idx, int L, int R, int l, int r, int v)
{
	l = max(L, l); r = min(R, r);
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) {lazy[idx] += v; prop(idx, L, R);}
		else
		{
			int M = L + R >> 1;
			upd(2 * idx, L, M, l, r, v);
			upd(2 * idx + 1, M + 1, R, l, r, v);
			seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

void init(int N, int A[], int B[]) 
{
	n = N;
	for (int i = 0; i < n; i++) {pref[B[i]]++; suf[A[i]]++;}
	for (int i = 1; i <= n + 1; i++) {pref[i] += pref[i - 1];}
	for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
	build(1, 1, n);
}

int can(int M, int K[]) 
{
	sort(K, K + M);
	for (int i = 0; i < M; i++)
	{
		upd(1, 1, n, 1, K[i], K[i]);
		upd(1, 1, n, 1, K[i], suf[K[i] + 1]);
		if (seg[1] > n) {return 0;} 
		upd(1, 1, n, 1, K[i], -suf[K[i] + 1]);
	}
	for (int i = 0; i < M; i++)
	{
		upd(1, 1, n, 1, K[i], -K[i]);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:18:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void upd(int, int, int, int, int, int)':
teams.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |    int M = L + R >> 1;
      |            ~~^~~

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