Submission #288927

#	Time	Username	Problem	Language	Result	Execution time	Memory
288927		Berted	Teams (IOI15_teams)	C++14	0 / 100	1211 ms	228688 KiB

teams

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

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

using namespace std;

struct p_node
{
	int v = 0, l = -1, r = -1;
	p_node() {}
};

int n, seg[SZ], lazy[SZ], pref[SZ2], suf[SZ2];
vector<p_node> p_seg;
vector<int> dt[SZ2];
int p_idx[SZ2];

void p_build(int idx, int L, int R)
{
	if (L < R)
	{
		int M = L + R >> 1;
		p_seg.push_back(p_node()); p_seg.push_back(p_node());
		p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
		p_build(p_seg[idx].l, L, M);
		p_build(p_seg[idx].r, M + 1, R);
	}
}

void p_upd(int idx, int odx, int L, int R, int x)
{
	if (L <= R)
	{
		if (L == x && x == R) {p_seg[idx].v = p_seg[odx].v + x;}
		else
		{
			int M = L + R >> 1;
			p_seg.push_back(p_node());
			if (x <= M) 
			{
				p_seg[idx].l = p_seg.size() - 1;
				p_seg[idx].r = p_seg[odx].r;
				p_upd(p_seg[idx].l, p_seg[odx].l, L, M, x);
			}
			else
			{
				p_seg[idx].r = p_seg.size() - 1;
				p_seg[idx].l = p_seg[odx].l;
				p_upd(p_seg[idx].r, p_seg[odx].r, M + 1, R, x);
			}
			p_seg[idx].v = p_seg[p_seg[idx].l].v + p_seg[p_seg[idx].r].v;
		}
	}
}

int p_qry(int idx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(R, r);
	if (l <= r)
	{
		if (L == l && R == r) {return p_seg[idx].v;}
		else
		{
			int M = L + R >> 1;
			return p_qry(p_seg[idx].l, L, M, l, r) + p_qry(p_seg[idx].r, M + 1, R, l, r);
		}
	}
	return 0;
}

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]]++;
		dt[B[i]].push_back(A[i]);
	}
	p_seg.push_back(p_node());
	p_idx[0] = p_seg.size() - 1;
	p_build(p_idx[0], 1, n);
	for (int i = 1; i <= n; i++)
	{
		p_idx[i] = p_idx[i - 1];
		for (auto &x : dt[i])
		{
			int nidx = p_seg.size();
			p_seg.push_back(p_node());
			p_upd(nidx, p_idx[i], 1, n, x);
			p_idx[i] = nidx;
		}
	}
	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[]) 
{
	//cout << "New " << M << "\n";
	sort(K, K + M);
	int ret = 1;
	for (int i = 0; i < M; i++)
	{
		upd(1, 1, n, 1, K[i], K[i]);
		if (i) 
		{
			//cout << i << " " << p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1) << "\n";
			upd(1, 1, n, 1, K[i - 1], p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1));
		}
		upd(1, 1, n, 1, K[i], suf[K[i] + 1]);
		if (seg[1] > n) {ret = 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]);
		if (i) {upd(1, 1, n, 1, K[i - 1], -p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1));}
	}
	return ret;
}

Compilation message (stderr)

teams.cpp: In function 'void p_build(int, int, int)':
teams.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp:28:31: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   28 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                  ~~~~~~~~~~~~~^~~
teams.cpp:28:64: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   28 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                                                   ~~~~~~~~~~~~~^~~
teams.cpp: In function 'void p_upd(int, int, int, int, int)':
teams.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp:45:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   45 |     p_seg[idx].l = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp:51:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |     p_seg[idx].r = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int p_qry(int, int, int, int, int)':
teams.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:82:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void upd(int, int, int, int, int, int)':
teams.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:130:26: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  130 |  p_idx[0] = p_seg.size() - 1;
      |             ~~~~~~~~~~~~~^~~
teams.cpp:137:25: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  137 |    int nidx = p_seg.size();
      |               ~~~~~~~~~~^~

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