oj.uz

Submission #228680

# Submission time Handle Problem Language Result Execution time Memory
228680 2020-05-02T10:42:26 Z mieszko11b Teams (IOI15_teams) C++14
100 / 100
 1928 ms 398608 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 129528 KB Output is correct
2 Correct 64 ms 129528 KB Output is correct
3 Correct 73 ms 129528 KB Output is correct
4 Correct 77 ms 129528 KB Output is correct
5 Correct 65 ms 129632 KB Output is correct
6 Correct 68 ms 129532 KB Output is correct
7 Correct 66 ms 129528 KB Output is correct
8 Correct 66 ms 129528 KB Output is correct
9 Correct 66 ms 129528 KB Output is correct
10 Correct 66 ms 129528 KB Output is correct
11 Correct 66 ms 129528 KB Output is correct
12 Correct 68 ms 129528 KB Output is correct
13 Correct 66 ms 129528 KB Output is correct
14 Correct 65 ms 129528 KB Output is correct
15 Correct 65 ms 129528 KB Output is correct
16 Correct 70 ms 129528 KB Output is correct
17 Correct 69 ms 129512 KB Output is correct
18 Correct 66 ms 129528 KB Output is correct
19 Correct 68 ms 129528 KB Output is correct
20 Correct 67 ms 129504 KB Output is correct
21 Correct 65 ms 129528 KB Output is correct
22 Correct 65 ms 129528 KB Output is correct
23 Correct 66 ms 129528 KB Output is correct
24 Correct 67 ms 129528 KB Output is correct
25 Correct 76 ms 129528 KB Output is correct
26 Correct 68 ms 129528 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 177912 KB Output is correct
2 Correct 188 ms 177788 KB Output is correct
3 Correct 184 ms 177784 KB Output is correct
4 Correct 184 ms 177844 KB Output is correct
5 Correct 141 ms 177784 KB Output is correct
6 Correct 144 ms 177784 KB Output is correct
7 Correct 151 ms 177784 KB Output is correct
8 Correct 133 ms 177912 KB Output is correct
9 Correct 134 ms 177912 KB Output is correct
10 Correct 149 ms 177784 KB Output is correct
11 Correct 132 ms 177912 KB Output is correct
12 Correct 138 ms 177912 KB Output is correct
13 Correct 152 ms 177784 KB Output is correct
14 Correct 158 ms 177912 KB Output is correct
15 Correct 182 ms 177912 KB Output is correct
16 Correct 171 ms 177912 KB Output is correct
17 Correct 143 ms 177784 KB Output is correct
18 Correct 134 ms 177784 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 177840 KB Output is correct
2 Correct 262 ms 177872 KB Output is correct
3 Correct 559 ms 180456 KB Output is correct
4 Correct 197 ms 177784 KB Output is correct
5 Correct 359 ms 177784 KB Output is correct
6 Correct 328 ms 177784 KB Output is correct
7 Correct 353 ms 177912 KB Output is correct
8 Correct 303 ms 177784 KB Output is correct
9 Correct 134 ms 177912 KB Output is correct
10 Correct 135 ms 177784 KB Output is correct
11 Correct 137 ms 177904 KB Output is correct
12 Correct 213 ms 177912 KB Output is correct
13 Correct 413 ms 177912 KB Output is correct
14 Correct 585 ms 179132 KB Output is correct
15 Correct 270 ms 177888 KB Output is correct
16 Correct 264 ms 177788 KB Output is correct
17 Correct 249 ms 177888 KB Output is correct
18 Correct 209 ms 177912 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 390392 KB Output is correct
2 Correct 834 ms 390520 KB Output is correct
3 Correct 1928 ms 393924 KB Output is correct
4 Correct 711 ms 397176 KB Output is correct
5 Correct 1378 ms 394420 KB Output is correct
6 Correct 1310 ms 394488 KB Output is correct
7 Correct 1382 ms 394488 KB Output is correct
8 Correct 1325 ms 394488 KB Output is correct
9 Correct 411 ms 395000 KB Output is correct
10 Correct 409 ms 393168 KB Output is correct
11 Correct 447 ms 393592 KB Output is correct
12 Correct 687 ms 394020 KB Output is correct
13 Correct 1320 ms 395796 KB Output is correct
14 Correct 1897 ms 398608 KB Output is correct
15 Correct 883 ms 397000 KB Output is correct
16 Correct 899 ms 397304 KB Output is correct
17 Correct 722 ms 396408 KB Output is correct
18 Correct 704 ms 396536 KB Output is correct