Submission #384632

#	Time	Username	Problem	Language	Result	Execution time	Memory
384632		LucaDantas	Teams (IOI15_teams)	C++17	34 / 100	4108 ms	367940 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
 
#define ff first
#define ss second
 
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

constexpr int maxn = 5e5+10, SZ = 100;

std::priority_queue<int, std::vector<int>, std::greater<int>> q;

int a[maxn], b[maxn], n;

pii range[maxn];
 
int ind[maxn];
 
int opt[maxn];
 
struct Node
{
	Node *l, *r;
	int v;
 
	Node()
	{
		l = r = NULL;
		v = 0;
	}
} *version[maxn];
 
struct PersistentSegmentTree
{
	void build(Node *node, int l, int r)
	{
		if (l == r) return;
 
		int mid = (l+r)>>1;
 
		node->l = new Node(); node->r = new Node();
 
		build(node->l, l, mid); build(node->r, mid+1, r);
	}
 
	void upd(Node *prev, Node *node, int l, int r, int pos, int v)
	{
		if (l == r)
		{
			node->v = prev->v + v;
			return;
		}
 
		int mid = (l+r)>>1;
 
		if (pos <= mid)
		{
			if (!node->l) node->l = new Node();
			node->r = prev->r;
 
			upd(prev->l, node->l, l, mid, pos, v);
		}
		else
		{
			if (!node->r) node->r = new Node();
			node->l = prev->l;
 
			upd(prev->r, node->r, mid+1, r, pos, v);
		}
 
		node->v = node->l->v + node->r->v;
	}
 
	int query(Node *prev, Node *node, int l, int r, int a, int b)
	{
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return node->v - prev->v;
 
		int mid = (l+r)>>1;
 
		return query(prev->l, node->l, l, mid, a, b) + query(prev->r, node->r, mid+1, r, a, b);
	}
 
	int get(int l, int r, int k)
	{
		return query(version[ind[l]], version[ind[r]], 1, n, k, n);
	}
} seg;

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < N; i++)
		a[i] = A[i], b[i] = B[i];

	for (int i = 1; i <= n; i++)
		range[i] = {A[i-1], B[i-1]};
 
	sort(range+1, range+n+1);
 
	int ptr = 1, aux = 0;
 
	version[0] = new Node();
	seg.build(version[0], 1, n);
 
	for (int i = 1; i <= n; i++)
	{
		while (ptr <= n && range[ptr].ff == i)
		{
			version[++aux] = new Node();
			seg.upd(version[aux-1], version[aux], 1, n, range[ptr].ss, 1);
			ptr++;
		}
 
		ind[i] = aux;
	}
}

struct Event
{
	int t, x, r;
	bool operator<(Event e) { if(x == e.x) return t < e.t; return x < e.x; }
};

std::vector<Event> events;

int greedy(int M, int K[]) {
	events.clear();
	while(q.size()) q.pop();
	for(int i = 0; i < n; i++)
		events.push_back({0, a[i], b[i]});
	for(int i = 0; i < M; i++)
		events.push_back({1, K[i], K[i]});
	std::sort(events.begin(), events.end());
	for(auto e : events) {
		while(q.size() && q.top() < e.x)
			q.pop();
		if(!e.t) q.push(e.r);
		else {
			while(e.r--) {
				if(!q.size()) return 0;
				q.pop();
			}
		}
	}
	return 1;
}

ll dp[maxn];
int fq[maxn];

void solve(vector<int> &V, int l, int r)
{
	if (l > r) return;
 
	for (int i = 0; i < V.size(); i++)
	{
		int k = V[i];
		dp[i] = 1ll*seg.get(0, k, k) - 1ll*fq[k]*k;
 
		for (int j = 0; j < i; j++)
			dp[i] = min(dp[i], dp[j] + 1ll*seg.get(V[j], k, k) - 1ll*fq[k]*k);
	}
}

int can(int M, int K[]) {
	if(M > 50) return greedy(M, K);

	int m = M;
	vector<int> V;
 
	for (int i = 0; i < m; i++)
	{
		V.push_back(K[i]);
		fq[K[i]]++;
	}
 
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
 
	m = V.size();
 
	solve(V, 0, m-1);
 
	bool ok = 1;
 
	for (int j = 0; j < m; j++)
	{
		if (dp[j] < 0) ok = 0;
 
		dp[j] = fq[V[j]] = opt[j] = 0;
	}
 
	return ok;
}

Compilation message (stderr)

teams.cpp: In member function 'int PersistentSegmentTree::query(Node*, Node*, int, int, int, int)':
teams.cpp:78:2: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   78 |  {
      |  ^
teams.cpp:16:14: note: shadowed declaration is here
   16 | int a[maxn], b[maxn], n;
      |              ^
teams.cpp:78:2: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   78 |  {
      |  ^
teams.cpp:16:5: note: shadowed declaration is here
   16 | int a[maxn], b[maxn], n;
      |     ^
teams.cpp: In function 'void solve(std::vector<int>&, int, int)':
teams.cpp:158:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |  for (int i = 0; i < V.size(); i++)
      |                  ~~^~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:183:12: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  183 |  m = V.size();
      |      ~~~~~~^~

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