Submission #290587

#	Time	Username	Problem	Language	Result	Execution time	Memory
290587		Berted	Teams (IOI15_teams)	C++14	13 / 100	1671 ms	225196 KiB

teams

#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, ll>
#define fst first
#define snd second
#define ppp pair<pii, pii>

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, suf[SZ2], seg[SZ], lazy[SZ];
vector<p_node> p_seg;
vector<int> dt[SZ2];
int p_idx[SZ2];
vector<ppp> ivl;

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 + 1;}
		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;
}

inline void prop(int idx, int L, int R)
{
	if (L <= R && lazy[idx] != -1)
	{
		seg[idx] = p_seg[lazy[idx]].v;
		if (L < R)
		{
			lazy[2 * idx] = p_seg[lazy[idx]].l;
			lazy[2 * idx + 1] = p_seg[lazy[idx]].r;
		}
		lazy[idx] = -1;
	}
}

void bld(int idx, int L, int R)
{
	seg[idx] = 0; lazy[idx] = -1;
	if (L < R)
	{
		int M = L + R >> 1;
		bld(2 * idx, L, M);
		bld(2 * idx + 1, M + 1, R);
	}
}

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

void updi(int idx, int L, int R, int x, int v)
{
	prop(idx, L, R);
	if (L == x && x == R) {seg[idx] += v;}
	else
	{
		int M = L + R >> 1;
		if (x <= M) {updi(2 * idx, L, M, x, v);}
		else {updi(2 * idx + 1, M + 1, R, x, v);}
		seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
	}
}

inline void getInterval(int idx, int edx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(r, R);
	prop(edx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) {ivl.push_back({{idx, edx}, {L, R}});}
		else 
		{
			int M = L + R >> 1;
			getInterval(p_seg[idx].l, 2 * edx, L, M, l, r);
			getInterval(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r);
		}
	}
}

inline int findPos(int idx, int edx, int L, int R, int x)
{
	prop(edx, L, R);
	//cout << "FindPos " << L << " " << R << " " << x << " " << p_seg[idx].v - seg[edx] << "\n";
	if (L < R)
	{
		int M = L + R >> 1;
		if (p_seg[p_seg[idx].l].v - seg[2 * edx] >= x) {return findPos(p_seg[idx].l, 2 * edx, L, M, x);}
		else {return findPos(p_seg[idx].r, 2 * edx + 1, M + 1, R, x - p_seg[p_seg[idx].l].v + seg[2 * edx]);}
	}
	else {return L + (x >= p_seg[idx].v - seg[edx]);}
}

int qry(int idx, int edx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(r, R);
	prop(edx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) 
		{
			return p_seg[idx].v - seg[edx];
		}
		else
		{
			int M = L + R >> 1;
			return qry(p_seg[idx].l, 2 * edx, L, M, l, r) + qry(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r);
		}
	}
	return 0;
}

void init(int N, int A[], int B[]) 
{
	n = N;
	for (int i = 0; i < n; i++) 
	{
		suf[A[i]]++;
		dt[A[i]].push_back(B[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 = n; i >= 0; i--) {suf[i] += suf[i + 1];}
	bld(1, 1, n);
}

int can(int M, int K[]) 
{
	//cout << "New " << M << "\n";
	upds(1, p_idx[0], 1, n, 1, n);
	sort(K, K + M); 
	for (int i = 0; i < M; i++)
	{
		if (qry(p_idx[K[i]], 1, 1, n, K[i], n) < K[i]) {return 0;}
		else
		{
			ivl.clear();
			getInterval(p_idx[K[i]], 1, 1, n, K[i], n - 1);
			int L = K[i], v = K[i];
			for (int i = 0; i < ivl.size(); i++)
			{
				if (p_seg[ivl[i].fst.fst].v - seg[ivl[i].fst.snd] < v) 
				{
					v -= p_seg[ivl[i].fst.fst].v - seg[ivl[i].fst.snd];
					L = ivl[i].snd.snd + 1;
				}
				else {L = findPos(ivl[i].fst.fst, ivl[i].fst.snd, ivl[i].snd.fst, ivl[i].snd.snd, v); break;}
			}
			//cout << "LOL: " << i << " " << L << "\n";
			updi(1, 1, n, L, K[i] - qry(p_idx[K[i]], 1, 1, n, K[i], L - 1));
			upds(1, p_idx[K[i]], 1, n, K[i], L - 1);
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void p_build(int, int, int)':
teams.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp:34:31: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                  ~~~~~~~~~~~~~^~~
teams.cpp:34:64: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |   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:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |    int M = L + R >> 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].l = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp:57:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   57 |     p_seg[idx].r = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int p_qry(int, int, int, int, int)':
teams.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void bld(int, int, int)':
teams.cpp:100:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp: In function 'void upds(int, int, int, int, int, int)':
teams.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void updi(int, int, int, int, int)':
teams.cpp:133:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp: In function 'void getInterval(int, int, int, int, int, int)':
teams.cpp:149:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'int findPos(int, int, int, int, int)':
teams.cpp:162:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp: In function 'int qry(int, int, int, int, int, int)':
teams.cpp:181:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:197:26: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  197 |  p_idx[0] = p_seg.size() - 1;
      |             ~~~~~~~~~~~~~^~~
teams.cpp:204:25: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  204 |    int nidx = p_seg.size();
      |               ~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:227:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
  227 |    for (int i = 0; i < ivl.size(); i++)
      |             ^
teams.cpp:219:11: note: shadowed declaration is here
  219 |  for (int i = 0; i < M; i++)
      |           ^
teams.cpp:227:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, long long int>, std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |    for (int i = 0; i < ivl.size(); i++)
      |                    ~~^~~~~~~~~~~~
teams.cpp:232:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  232 |      L = ivl[i].snd.snd + 1;
teams.cpp:9:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    9 | #define snd second
teams.cpp:234:50: note: in expansion of macro 'snd'
  234 |     else {L = findPos(ivl[i].fst.fst, ivl[i].fst.snd, ivl[i].snd.fst, ivl[i].snd.snd, v); break;}
      |                                                  ^~~
teams.cpp:9:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    9 | #define snd second
teams.cpp:234:82: note: in expansion of macro 'snd'
  234 |     else {L = findPos(ivl[i].fst.fst, ivl[i].fst.snd, ivl[i].snd.fst, ivl[i].snd.snd, v); break;}
      |                                                                                  ^~~

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