Submission #406374

#	Time	Username	Problem	Language	Result	Execution time	Memory
406374		pure_mem	Teams (IOI15_teams)	C++14	77 / 100	1631 ms	371108 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 5e5 + 12, BS = 300;

struct node{
	int val = 0;
	node *l = nullptr, *r = nullptr;
	node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
		val = _val, l = _l, r = _r;
	}
};
int getVal(node* v){
	return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
	if(tl == tr) return new node(getVal(v) + val);
	int tm = (tl + tr) / 2;
	if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
	else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
	v->val = getVal(v->l) + getVal(v->r);
	return v;
}
int get(node* v, int tl, int tr, int l, int r){
	if(tl > r || l > tr) return 0;
	if(tl >= l && tr <= r) return getVal(v);
	int tm = (tl + tr) / 2;
	return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];

int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];

void init(int N, int A[], int B[]) {
	n = N, root[0] = new node();
	for(int i = 0;i < n;i++)
		rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
	for(int i = 1;i <= n;i++){
		root[i] = root[i - 1];
		for(int v: rv[i]){
			root[i] = upd(root[i], 1, n, v, 1);
		}
	}			
}

int cf(int l, int r){
	return get(root[n - r + 1], 1, n, l, r);
}

int can(int M, int K[]) {
	sort(K, K + M);
  	vector< int > opt; int ptr = -1;
  	for(int i = 0;i < M;i++){
  		dp[i] = cf(1, K[i]) - K[i];
  		while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) <= dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--;
  		if(ptr >= 0) dp[i] = min(dp[i], dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i]) - K[i]);
  		ptr++, opt.push_back(i);
  		while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) <= dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--;
  		if(dp[i] < 0) return 0;
  	}
	return 1;
}

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