Submission #133079

#	Time	Username	Problem	Language	Result	Execution time	Memory
133079		MAMBA	Teams (IOI15_teams)	C++17	100 / 100	2019 ms	360696 KiB

teams

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

using namespace std;

#define rep(i , j ,k) for (int i = j; i < (int)k; i++)
#define lid id<<1
#define rid lid|1

typedef pair<int , int> pii;
typedef vector<int> vi;

inline bool smax(int &a, int b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

const int MAXN = 5e5 + 10;

int N;
pii arr[MAXN];

vi seg[MAXN << 2], Lp[MAXN << 2] , Rp[MAXN << 2];
int rem[MAXN << 2] , lazy[MAXN << 2];

void build(int l = 0, int r = N, int id = 1) {

	rem[id] = 0;
	lazy[id] = 0;

	seg[id].resize(r - l);
	Lp[id].resize(r - l + 1);
	Rp[id].resize(r - l + 1);

	if (l == r - 1) {
		seg[id][0] = arr[l].second;
		return;
	}

	int mid = l + r >> 1;
	build(l , mid , lid);
	build(mid , r ,rid);

	int lptr = 0, rptr = 0;
	int lsz = mid - l, rsz = r - mid;

	auto Lm = [&]() {
		int pos = lptr + rptr;
		Lp[id][pos] = lptr;
		Rp[id][pos] = rptr;
		seg[id][pos] = seg[lid][lptr++];
	};

	auto Rm = [&]() {
		int pos = lptr + rptr;
		Lp[id][pos] = lptr;
		Rp[id][pos] = rptr;
		seg[id][pos] = seg[rid][rptr++];
	};


	while (lptr < lsz && rptr < rsz) 
		seg[lid][lptr] < seg[rid][rptr] ? Lm() : Rm();	
	while (lptr < lsz) Lm();
	while (rptr < rsz) Rm();
	Lp[id][lptr + rptr] = lptr;
	Rp[id][lptr + rptr] = rptr;

}

inline void shift(int id) { 
	smax(lazy[lid] , Lp[id][lazy[id]]);
	smax(lazy[rid] , Rp[id][lazy[id]]);
	smax(rem[lid] , lazy[lid]);
	smax(rem[rid] , lazy[rid]);
	rem[id] = rem[lid] + rem[rid];
}

void segRem(int pos , int p2 , int& need , int l = 0, int r = N, int id= 1) {
	if (r <= pos || need <= 0 || p2 <= rem[id]) return;
	if (l >= pos && p2 - rem[id] <= need ) {
		need -= p2 - rem[id];
		rem[id] = p2;
		lazy[id] = p2;
		return;
	}
	int mid = l + r >> 1;
	shift(id);
	segRem(pos , Lp[id][p2] , need , l , mid , lid);
	segRem(pos , Rp[id][p2] , need , mid , r,  rid);
	rem[id] = rem[lid] + rem[rid];
}

void segClear(int l = 0, int r = N, int id = 1) {
	lazy[id] = rem[id] = 0;
	if (l == r - 1) return;
	int mid = l + r >> 1;
	if (rem[lid]) segClear(l , mid , lid);
	if (rem[rid]) segClear(mid , r, rid);
}


void init(int N2, int A[], int B[]) {
	N = N2;
	rep(i , 0 , N)
		arr[i] = pii(B[i] , A[i]);
	sort(arr ,arr + N);
	build();
}

int can(int M, int K[]) {
	bool flag = true;
	sort(K , K + M);
	for (int i = 0; i < M && flag; i++) {
		int id = lower_bound(arr, arr + N , pii(K[i] , -1)) - arr;
		int id2 = upper_bound(seg[1].begin() , seg[1].end() , K[i]) - seg[1].begin();
		int need = K[i];
		segRem(id , id2 , need);
		if (need) 
			flag = false;
	}
	segClear();
	return flag ? 1 : 0;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
teams.cpp: In function 'void segRem(int, int, int&, int, int, int)':
teams.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
teams.cpp: In function 'void segClear(int, int, int)':
teams.cpp:100:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:118:55: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int id = lower_bound(arr, arr + N , pii(K[i] , -1)) - arr;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
teams.cpp:119:63: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int id2 = upper_bound(seg[1].begin() , seg[1].end() , K[i]) - seg[1].begin();
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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