Submission #284462

#	Time	Username	Problem	Language	Result	Execution time	Memory
284462		nvmdava	Teams (IOI15_teams)	C++17	0 / 100	1400 ms	524292 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
 
struct Node{
	int l, r, s;
	Node *L, *R;
	Node(int _l, int _r, int _s, Node *_L, Node *_R){
		l = _l; r = _r; s = _s; L = _L; R = _R;
	}
 
	int query(int le, int ri){
		if(le > r || ri < l) return 0;
		if(le <= l && r <= ri) return s;
		return L -> query(le, ri) + R -> query(le, ri);
	}
 
	Node* update(int x){
		if(l > x || r < x) return this;
		if(l == r) return new Node(l, r, s + 1, L, R);
		return new Node(l, r, s + 1, L -> update(x), R -> update(x));
	}
 
	void build(){
		if(l == r) return;
		int m = (l + r) >> 1;
		L = new Node(l, m, 0, NULL, NULL);
		R = new Node(m + 1, r, 0, NULL, NULL);
		L -> build();
		R -> build();
	}
};
 
vector<int> lol[500005];
 
Node* tree[500005];
 
int query(int x1, int y1, int x2, int y2){
	--y1;
	return tree[y2] -> query(x1, x2) - tree[y1] -> query(x1, x2);
}
 
void init(int N, int A[], int B[]) {
	for(int i = 0; i < N; ++i)
		lol[B[i]].push_back(A[i]);
	tree[0] = new Node(1, N, 0, NULL, NULL);
	tree[0] -> build();
	for(int i = 1; i <= 500004; ++i){
		tree[i] = tree[i - 1];
		for(auto& x : lol[i]){
			tree[i] = tree[i] -> update(x);
		}
	}
}
 
int le[500005];
vector<pair<int, int> > idk;
vector<int> val;
int can(int M, int K[]) {
	sort(K + 0, K + M);
	val.clear();
	for(int i = 0; i < M; ++i){
		if(val.empty() || val.back() != K[i])
			val.push_back(K[i]);
		le[val.size() - 1] += K[i];
	}
	M = val.size();
	val.push_back(500005);
	idk = {{1, M}};
 
	for(int i = 0; i < M; ++i){
		int br = i;
		int s;
		while(idk.back().ss <= i) idk.pop_back();
		while((s = query(idk.back().ff, val[br], val[i], val[idk.back().ss] - 1)) < le[i]){
			le[i] -= s;
			br = idk.back().ss;
			idk.pop_back();
			if(idk.empty()) return 0;
		}
		for(int j = 20; j >= 0; --j){
			if(br + (1 << j) <= idk.back().ss && (s = query(idk.back().ff, val[br], val[i], val[br + (1 << j)] - 1)) < le[i]){
				le[i] -= s;
				br += 1 << j;
			}
		}
		le[br + 1] += le[i];
		while(!idk.empty() && idk.back().ss <= br)
			idk.pop_back();
		idk.push_back({val[i] + 1, br});
	}
 
 
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:69:14: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |  M = val.size();
      |      ~~~~~~~~^~

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