Submission #290356

#	Time	Username	Problem	Language	Result	Execution time	Memory
290356		Berted	Teams (IOI15_teams)	C++14	13 / 100	1143 ms	225820 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

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];
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 + 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;
		}
	}
	//cout << "UPD " << L << " " << R << " " << x << " " << p_seg[idx].v << "\n";
}

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 int ask(int L, int R) {return p_qry(p_idx[R], 1, n, L, R);}

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

int can(int M, int K[]) 
{
	//cout << "New " << M << "\n";
	vector<pii> k, s;
	sort(K, K + M); 
	for (int i = 0; i < M; i++)
	{
		if (k.size() && k.back().fst == K[i]) {k.back().snd += K[i];}
		else {k.push_back({K[i], K[i]});}
	}
	ll ret = 0, cur = 0;
	for (int i = 0; i < k.size(); i++)
	{
		cur += ask((s.size() ? (s.back().fst + 1) : 1), k[i].fst - 1);
		cur += k[i].snd;
		while (s.size())
		{
			if (s.size() > 1)
			{
				ll v1 = s.back().snd + ask(s.back().fst + 1, k[i].fst - 1) + ask(s[s.size() - 2].fst + 1, s.back().fst - 1), v2 = ask(s[s.size() - 2].fst + 1, k[i].fst - 1);
				if (v1 <= v2) {cur -= v1; cur += v2; s.pop_back();}
				else {break;}
			}
			else
			{
				ll v1 = s.back().snd + ask(s.back().fst + 1, k[i].fst - 1) + ask(1, s.back().fst - 1), v2 = ask(1, k[i].fst - 1);
				if (v1 <= v2) {cur -= v1; cur += v2; s.pop_back();}
				else {break;}
			}
		}
		s.push_back(k[i]);
		ret = max(ret, cur + suf[k[i].fst + 1]);
	}
	return ret <= n;
}

Compilation message (stderr)

teams.cpp: In function 'void p_build(int, int, int)':
teams.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp:32:31: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                  ~~~~~~~~~~~~~^~~
teams.cpp:32:64: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |   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:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp:49:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |     p_seg[idx].l = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp:55:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   55 |     p_seg[idx].r = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int p_qry(int, int, int, int, int)':
teams.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:26: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   91 |  p_idx[0] = p_seg.size() - 1;
      |             ~~~~~~~~~~~~~^~~
teams.cpp:98:25: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   98 |    int nidx = p_seg.size();
      |               ~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (int i = 0; i < k.size(); i++)
      |                  ~~^~~~~~~~~~

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