Submission #774774

#	Time	Username	Problem	Language	Result	Execution time	Memory
774774		ngrace	Teams (IOI15_teams)	C++14	13 / 100	4045 ms	363208 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

struct node{
    node* l;
    node* r;
    int sum;
    node(int val){
        l=nullptr;
        r=nullptr;
        sum=val;
    }
    node(node* lll, node* rr){
        l=lll;
        r=rr;
        sum=l->sum + r->sum;
    }
};
node* build(int l, int r){
    if(l==r) return new node(0);
    int m=(l+r)/2;
    return new node(build(l,m), build(m+1,r));
}
node* update(node* cur, int l, int r, int tar){
    if(l==r) return new node(cur->sum+1);
    int m=(l+r)/2;
    if(tar<=m) return new node(update(cur->l, l, m, tar), cur->r);
    return new node(cur->l, update(cur->r, m+1, r, tar));
}
int query(node* cur, int l, int r, int ql){
    if(ql<=l) return cur->sum;
    int m=(l+r)/2, ret=0;
    if(ql<=m) ret += query(cur->l, l, m, ql);
    ret += query(cur->r, m+1, r, ql);
	return ret;
}

int n;
v<ii> points;
v<node*> roots;
int getRect(int x1, int x2, int y){
	ii p1 = {x1, -1}, p2 = {x2+1, -1};
	int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
	int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
	return query(roots[ind2], 1, n, y) - query(roots[ind1], 1, n, y);
}

void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0; i<n; i++) points.push_back({A[i], B[i]});

	roots.push_back(build(1,n));
	sort(points.begin(), points.end());
	for(ii it:points) roots.push_back(update(roots.back(), 1, n, it.se));
}

int cnt=0;
int can(int M, int K[]) {
	sort(K, K+M);

	if(M>300){
		priority_queue<ii> pq;
		int j=0;
		for(int i=0; i<M; i++){
			while(j<n && points[j].fi<=K[i]){
				pq.push({-points[j].se, points[j].fi});
				j++;
			}
			while(pq.size()>0 && -pq.top().fi<K[i]) pq.pop();
			if(pq.size()<K[i]) return 0;
			for(int k=0; k<K[i]; k++) pq.pop();
		}
		return 1;
	}

	v<int> dp(M);
	stack<int> opt;
	for(int i=0; i<M; i++){
		dp[i] = getRect(0, K[i], K[i]) - K[i];
		while(opt.size()>2){
			int j2 = opt.top();
			opt.pop();
			int j1 = opt.top();
			opt.push(j2);
			int one = dp[j1] + (K[i]==K[j1] ? 0 : getRect(K[j1]+1, K[i], K[i]));
			int two = dp[j2] + (K[i]==K[j2] ? 0 : getRect(K[j2]+1, K[i], K[i]));
			if(one<=two) opt.pop();
			else break;
		}
		if(opt.size()>0){
			int j=opt.top();
			dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
		}
		if(dp[i]<0) return 0;
		opt.push(i);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:49:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   49 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:50:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   50 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:76:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |    if(pq.size()<K[i]) return 0;
      |       ~~~~~~~~~^~~~~

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