Submission #228680

#	Time	Username	Problem	Language	Result	Execution time	Memory
228680		mieszko11b	Teams (IOI15_teams)	C++14	100 / 100	1928 ms	398608 KiB

teams

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

using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define X first
#define Y second

struct SegmentTree {
	int lv;
	int n;
	vector<int> x[1100007], gel[1100007], lel[1100007], ger[1100007], ler[1100007];
	int y[600007];
	
	SegmentTree(int n, int A[], int B[]) {
		lv = 2;
		this->n = n;
		while(lv < n + 2)
			lv *= 2;
			
		vector<ii> V(n);
		for(int i = 0 ; i < n ; i++)
			V[i] = {B[i], A[i]};
		sort(V.begin(), V.end());
		
		for(int i = 0 ; i < n ; i++) {
			y[i] = V[i].X;
			x[lv + i].push_back(V[i].Y);
		}
		
		for(int i = lv - 1 ; i >= 1 ; i--) {
			int l = 2 * i;
			int r = 2 * i + 1;
			
			x[i].resize(x[l].size() + x[r].size());
			merge(x[l].begin(), x[l].end(), x[r].begin(), x[r].end(), x[i].begin());
			
			int ind;
			
			ind = 0;
			gel[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind < x[l].size() && x[l][ind] < x[i][j])
					ind++;
				gel[i][j] = ind;
			}
			
			ind = 0;
			ger[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind < x[r].size() && x[r][ind] < x[i][j])
					ind++;
				ger[i][j] = ind;
			}
			
			ind = -1;
			lel[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind + 1 < x[l].size() && x[l][ind + 1] <= x[i][j])
					ind++;
				lel[i][j] = ind;
			}
			
			ind = -1;
			ler[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind + 1 < x[r].size() && x[r][ind + 1] <= x[i][j])
					ind++;
				ler[i][j] = ind;
			}		
		}
	}
	
	int query(int a, int b, int l, int r, int w, int i1, int i2) {
		//~ cout << "q" << l << " " << r << " " << i1 << " " << i2 << endl;
		if(b < l || a > r || l > r || i1 > i2)
			return 0;
		if(a <= l && r <= b)
			return i2 - i1 + 1;
		return query(a, b, l, (l + r) / 2, 2 * w, gel[w][i1], lel[w][i2])
			 + query(a, b, (l + r) / 2 + 1, r, 2 * w + 1, ger[w][i1], ler[w][i2]);
	}
	
	int count(int x1, int x2, int y1, int y2) {
		//~ cout << x1 << " " << x2 << " " << y1 << " "<< y2 << endl;
		int a = lower_bound(y, y + n, y1) - y;
		int b = upper_bound(y, y + n, y2) - y - 1;
		if(a > b)
			return 0;
		int l = 0;
		int r = lv - 1;
		int w = 1;
		int i1 = lower_bound(x[w].begin(), x[w].end(), x1) - x[w].begin();
		int i2 = upper_bound(x[w].begin(), x[w].end(), x2) - x[w].begin() - 1;
		//~ cout << a << " " << b << " " << i1 << " " << i2 << " " << query(a, b, l, r, w, i1, i2) << endl;
		return query(a, b, l, r, w, i1, i2);
	}
	
	int query2(int l, int r, int w, ll maxv, int i1, int i2) {
		//~ cout << l << " " << r <<  " " << maxv <<  " " << i1 << " " << i2 << endl;
		if(maxv < 0)
			return 1e9;
		if(i1 > i2)
			return 0;
		if(l == r)
			return y[l];
		if(ler[w][i2] - ger[w][i1] + 1 <= maxv)
			return query2(l, (l + r) / 2, 2 * w, maxv - max(0, ler[w][i2] - ger[w][i1] + 1), gel[w][i1], lel[w][i2]);
		return query2((l + r) / 2 + 1, r, 2 * w + 1, maxv, ger[w][i1], ler[w][i2]);
	}
	
	int find_y(int x1, int x2, ll maxv) {
		int i1 = lower_bound(x[1].begin(), x[1].end(), x1) - x[1].begin();
		int i2 = upper_bound(x[1].begin(), x[1].end(), x2) - x[1].begin() - 1;
		//~ cout << x1 << " " << x2 << " " << maxv << " " << query2(0, lv - 1, 1, maxv, i1, i2) << endl;
		return query2(0, lv - 1, 1, maxv, i1, i2);	
	}
};

SegmentTree *ST;

void init(int N, int A[], int B[]) {
	ST = new SegmentTree(N, A, B);
}

ll dp[200007];

int can(int M, int K[]) {
	//~ cout << "hi" << endl;
	sort(K, K + M);
	set<int> cand;
	set<ii> Q;
	dp[0] = 0;
	cand.insert(0);
	vector<ii> V;
	V.emplace_back(0, 0);
	for(int i = 0 ; i < M ; i++) {
		int k = K[i];
		if(V.empty() || V.back().X != k)
			V.emplace_back(k, 1);
		else
			V.back().Y++;
	}
	
	ll res = 1e18;
	for(int i = 1 ; i < V.size() ; i++) {
		while(!Q.empty() && Q.begin()->X < V[i].X) {
			//~ for(int x : cand)
				//~ cout << x << " ";
			//~ cout << endl;
			int j = Q.begin()->Y;
			//~ cout << j << endl;
			Q.erase(Q.begin());
			auto it = cand.lower_bound(j);
			
			if(it == cand.end() || *it != j)
				continue;
			
			cand.erase(next(it));
			if(next(it) != cand.end()) {
				int k = *next(it);
				Q.insert({ST->find_y(V[j].X + 1, V[k].X, dp[k] - dp[j]), j});
			}
		}
		int j = *prev(cand.end());
		
		dp[i] = dp[j] + ST->count(V[j].X + 1, V[i].X, V[i].X, 1e9) - (ll)V[i].X * V[i].Y;
		res = min(res, dp[i]);
		
		//~ cout << i << " " << j << " " << dp[i] << endl;
		
		Q.insert({ST->find_y(V[j].X + 1, V[i].X, dp[i] - dp[j]), j});
		//~ cout << ST->find_y(V[j].X + 1, V[i].X, dp[i] - dp[j]) << endl;
		cand.insert(i);
	}
	
	return res >= 0;
}

Compilation message (stderr)

teams.cpp: In constructor 'SegmentTree::SegmentTree(int, int*, int*)':
teams.cpp:18:39: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
  SegmentTree(int n, int A[], int B[]) {
                                       ^
teams.cpp:14:6: note: shadowed declaration is here
  int n;
      ^
teams.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind < x[l].size() && x[l][ind] < x[i][j])
           ~~~~^~~~~~~~~~~~~
teams.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind < x[r].size() && x[r][ind] < x[i][j])
           ~~~~^~~~~~~~~~~~~
teams.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind + 1 < x[l].size() && x[l][ind + 1] <= x[i][j])
           ~~~~~~~~^~~~~~~~~~~~~
teams.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind + 1 < x[r].size() && x[r][ind + 1] <= x[i][j])
           ~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In member function 'int SegmentTree::count(int, int, int, int)':
teams.cpp:89:37: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int a = lower_bound(y, y + n, y1) - y;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:90:41: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int b = upper_bound(y, y + n, y2) - y - 1;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:96:54: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i1 = lower_bound(x[w].begin(), x[w].end(), x1) - x[w].begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:97:69: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i2 = upper_bound(x[w].begin(), x[w].end(), x2) - x[w].begin() - 1;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In member function 'int SegmentTree::find_y(int, int, ll)':
teams.cpp:116:54: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i1 = lower_bound(x[1].begin(), x[1].end(), x1) - x[1].begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:117:69: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i2 = upper_bound(x[1].begin(), x[1].end(), x2) - x[1].begin() - 1;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:149:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < V.size() ; i++) {
                  ~~^~~~~~~~~~

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