oj.uz

Submission #97425

# Submission time Handle Problem Language Result Execution time Memory
97425 2019-02-16T00:05:25 Z tincamatei Teams (IOI15_teams) C++14
77 / 100
 2628 ms 525312 KB 
#include "teams.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 500000;
const int NNODES = 15000000;

struct AintPersistent {
	AintPersistent *sl, *sr;
	int val;
	AintPersistent() {
		val = 0;
		sl = sr = NULL;
	}
} cache[NNODES];
int topcache;

vector<AintPersistent*> root;

AintPersistent* mynew() {
	return &cache[topcache++];
}

AintPersistent* init(int l = 1, int r = MAX_N) {
	AintPersistent *rez = mynew();
	if(l < r) {
		int mid = (l + r) / 2;
		rez->sl = init(l, mid);
		rez->sr = init(mid + 1, r);
	}
	return rez;
}
 
AintPersistent* updateDfs(int poz, int val, int l, int r, AintPersistent* T) {
	if(r < poz || poz < l) return T;
	if(l == r) {
		AintPersistent* rez = mynew();
		rez->val = T->val + val;
		return rez;
	} else {
		int mid = (l + r) / 2;
		AintPersistent* rez = mynew();
		rez->sl = updateDfs(poz, val, l, mid, T->sl);
		rez->sr = updateDfs(poz, val, mid + 1, r, T->sr);
		rez->val = rez->sl->val + rez->sr->val;
		return rez;
	}
}
 
int queryDfs(int i, int j, int l, int r, AintPersistent* T) {
	if(j < l || r < i || j < i) return 0;
	if(i <= l && r <= j)
		return T->val;
	else {
		int mid = (l + r) / 2;
		return queryDfs(i, j, l, mid, T->sl) +
					 queryDfs(i, j, mid + 1, r, T->sr);
	}
}
 
void update(int timestamp, int poz, int val) {
	root.push_back(updateDfs(poz, val, 1, MAX_N, root[timestamp]));
}
 
int query(int timestamp, int i, int j) {
	return queryDfs(i, j, 1, MAX_N, root[timestamp]);
}
 
pair<int, int> points[MAX_N];
int atable[1+MAX_N], btable[1+MAX_N];
 
// de jos in sus
bool bsort(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}
 
// de la stanga la dreapta
bool asort(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

int N;
 
int getRealA(int A) {
	int st = -1, dr = N;
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(atable[mid] <= A)
			st = mid;
		else
			dr = mid;
	}
	return st + 1;
}
 
int getRealB(int B) {
	int st = -1, dr = N;
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(btable[mid] <= B)
			st = mid;
		else
			dr = mid;
	}
	return st + 1;
}

int query(int a1, int b1, int a2, int b2) {
	return query(a2, b1, b2) - query(a1 - 1, b1, b2);
}

int binsrc(AintPersistent* plusTree, AintPersistent* minusTree, int val, int l, int r) {
	if(l == r) return l;

	int mid = (l + r) / 2;
	int lval = plusTree->sl->val - minusTree->sl->val;
	//printf("Aint data: %d %d %d %d\n", l, r, lval, val);
	if(lval >= val)
		return binsrc(plusTree->sl, minusTree->sl, val, l, mid);
	else
		return binsrc(plusTree->sr, minusTree->sr, val - lval, mid + 1, r);
}

void init(int _N, int A[], int B[]) {
	N = _N;
	
	root.push_back(init());
	for(int i = 0; i < N; ++i)
		points[i] = make_pair(A[i], B[i]);
	
	//printf("Original Points:\n");
	//for(int i = 0; i < N; ++i)
	//	printf("%d %d\n", points[i].first, points[i].second);

	sort(points, points + N, bsort);
	for(int i = 0; i < N; ++i) {
		btable[i] = points[i].second;
		points[i].second = i + 1;
	}
	
	sort(points, points + N, asort);
	for(int i = 0; i < N; ++i) {
		atable[i] = points[i].first;
		points[i].first = i + 1;
	}
	
	for(int i = 0; i < N; ++i)
		update(root.size() - 1, points[i].second, 1);
	
	//printf("NODES->%d %d\n", nodes, sizeof(AintPersistent));

	//printf("Transformed Points:\n");
	//for(int i = 0; i < N; ++i)
	//	printf("%d %d\n", points[i].first, points[i].second);
}

int can(int M, int K[]) {
	//printf("Query:\n%d\n", M);
	//for(int i = 0; i < M; ++i)
	//	printf("%d ", K[i]);
	//printf("\n");
	sort(K, K + M);
	vector<pair<int, int> > corners;
	corners.push_back(make_pair(0, MAX_N));
	for(int i = 0; i < M; ++i) {
		int ak = getRealA(K[i]),
		    bk = getRealB(K[i] - 1);
		//printf("Query Point: %d %d\n", ak, bk);

		//printf("Corners:\n");
		//for(auto it: corners)
		//	printf("%d %d\n", it.first, it.second);

		while(corners.back().second <= bk)
			corners.pop_back();
		while(!corners.empty() && K[i] > 0) {
			int x = query(corners.back().first + 1, bk + 1, ak, corners.back().second);
			if(x <= K[i]) {
				K[i] -= x;
				bk = corners.back().second;
				corners.pop_back();
			} else {
				int cut = query(corners.back().first + 1, 1, ak, bk);
				bk = binsrc(root[ak], root[corners.back().first], cut + K[i], 1, MAX_N);
				K[i] -= query(corners.back().first + 1, 1, ak, bk) - cut;
			}
		}

		corners.push_back(make_pair(ak, bk));

		if(K[i] > 0)
			return false;
	}
	return true;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:149:22: warning: conversion to 'int' from 'std::vector<AintPersistent*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   update(root.size() - 1, points[i].second, 1);
          ~~~~~~~~~~~~^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 352632 KB Output is correct
2 Correct 282 ms 352632 KB Output is correct
3 Correct 269 ms 352632 KB Output is correct
4 Correct 281 ms 352632 KB Output is correct
5 Correct 270 ms 352640 KB Output is correct
6 Correct 279 ms 352632 KB Output is correct
7 Correct 284 ms 352716 KB Output is correct
8 Correct 308 ms 352572 KB Output is correct
9 Correct 280 ms 352712 KB Output is correct
10 Correct 281 ms 352632 KB Output is correct
11 Correct 298 ms 352632 KB Output is correct
12 Correct 294 ms 352604 KB Output is correct
13 Correct 300 ms 352584 KB Output is correct
14 Correct 267 ms 352760 KB Output is correct
15 Correct 268 ms 352632 KB Output is correct
16 Correct 275 ms 352616 KB Output is correct
17 Correct 269 ms 352620 KB Output is correct
18 Correct 275 ms 352632 KB Output is correct
19 Correct 275 ms 352632 KB Output is correct
20 Correct 259 ms 352616 KB Output is correct
21 Correct 307 ms 352672 KB Output is correct
22 Correct 281 ms 352760 KB Output is correct
23 Correct 327 ms 352632 KB Output is correct
24 Correct 281 ms 352552 KB Output is correct
25 Correct 318 ms 352632 KB Output is correct
26 Correct 296 ms 352800 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 356192 KB Output is correct
2 Correct 453 ms 356208 KB Output is correct
3 Correct 434 ms 356208 KB Output is correct
4 Correct 401 ms 356208 KB Output is correct
5 Correct 484 ms 356280 KB Output is correct
6 Correct 338 ms 356308 KB Output is correct
7 Correct 348 ms 356208 KB Output is correct
8 Correct 331 ms 356192 KB Output is correct
9 Correct 408 ms 356224 KB Output is correct
10 Correct 387 ms 356208 KB Output is correct
11 Correct 332 ms 356124 KB Output is correct
12 Correct 345 ms 356200 KB Output is correct
13 Correct 448 ms 356208 KB Output is correct
14 Correct 437 ms 356080 KB Output is correct
15 Correct 470 ms 356108 KB Output is correct
16 Correct 544 ms 356252 KB Output is correct
17 Correct 385 ms 356288 KB Output is correct
18 Correct 375 ms 356180 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 356236 KB Output is correct
2 Correct 468 ms 356204 KB Output is correct
3 Correct 1070 ms 359048 KB Output is correct
4 Correct 412 ms 356268 KB Output is correct
5 Correct 481 ms 356256 KB Output is correct
6 Correct 551 ms 356208 KB Output is correct
7 Correct 372 ms 356192 KB Output is correct
8 Correct 432 ms 356212 KB Output is correct
9 Correct 416 ms 356168 KB Output is correct
10 Correct 525 ms 356304 KB Output is correct
11 Correct 652 ms 356236 KB Output is correct
12 Correct 725 ms 356180 KB Output is correct
13 Correct 1072 ms 356332 KB Output is correct
14 Correct 1107 ms 357740 KB Output is correct
15 Correct 520 ms 356332 KB Output is correct
16 Correct 548 ms 356352 KB Output is correct
17 Correct 503 ms 356316 KB Output is correct
18 Correct 530 ms 356212 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 369032 KB Output is correct
2 Correct 1230 ms 369240 KB Output is correct
3 Correct 2628 ms 375080 KB Output is correct
4 Correct 1197 ms 369248 KB Output is correct
5 Correct 991 ms 369072 KB Output is correct
6 Runtime error 1111 ms 525312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -