제출 #774947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774947		ngrace	팀들 (IOI15_teams)	C++14	77 / 100	4046 ms	209348 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{
    int l;
    int r;
    int sum;
};
int nodecnt=0;
v<node> nodes;
int newNode(int l, int r){
	int ndc = nodecnt++;
	nodes.push_back(node());
	nodes[ndc].l=l;
	nodes[ndc].r=r;
	nodes[ndc].sum = nodes[nodes[ndc].l].sum + nodes[nodes[ndc].r].sum;
	return ndc;
}
int build(int l, int r){
    if(l==r){
		nodes.push_back(node());
		nodes[nodecnt].l = -1;
		nodes[nodecnt].r = -1;
		nodes[nodecnt].sum=0;
		return nodecnt++;
	}
    int m=(l+r)/2;
	return newNode(build(l, m), build(m+1, r));
}
int update(int cur, int l, int r, int tar){
    if(l==r) {
		nodes.push_back(node());
		nodes[nodecnt].l = -1;
		nodes[nodecnt].r = -1;
		nodes[nodecnt].sum=nodes[cur].sum+1;
		return nodecnt++;
	}
    int m=(l+r)/2;
    if(tar<=m){
		return newNode(update(nodes[cur].l, l, m, tar), nodes[cur].r);
	}
	return newNode(nodes[cur].l, update(nodes[cur].r, m+1, r, tar));
}
int query(int cur, int l, int r, int ql){
    if(ql<=l) return nodes[cur].sum;
    int m=(l+r)/2, ret=0;
    if(ql<=m) ret += query(nodes[cur].l, l, m, ql);
    ret += query(nodes[cur].r, m+1, r, ql);
	return ret;
}
int binSearchQuery(int curl, int curr, int l, int r, int num){ 
	//returns last place where num<amount holds
	if(l==r) return l;
	int m=(l+r)/2;
	int amount = nodes[nodes[curr].r].sum - nodes[nodes[curl].r].sum;
	if(num >= amount) return binSearchQuery(nodes[curl].l, nodes[curr].l, l,m, num - amount);
	return binSearchQuery(nodes[curl].r, nodes[curr].r, m+1, r, num);
}
 
int n;
v<ii> points;
v<int> 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);
}
int getSplit(int x1, int x2, int num){
	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 binSearchQuery(roots[ind1], roots[ind2], 1, n, num) + 1;//the first place where the suffix sum is >= num
}
 
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>400){
		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);
	set<int> opt;
	v<stack<ii>> pq(M+1);
	dp[0] = getRect(0, K[0], K[0]) - K[0];
	opt.insert(0);
	if(dp[0]<0) return 0;
	for(int i=1; i<M; i++){
		dp[i] = getRect(0, K[i], K[i]) - K[i];
 
		while(pq[i].size()>0){
			int j1=pq[i].top().fi;
			int j2=pq[i].top().se;
			pq[i].pop();
			if(opt.find(j1)==opt.end() || opt.find(j2)==opt.end()) continue;
			opt.erase(j2);
		}
 
		auto it=opt.end();
		it--;
		int j=*it;
		dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
		if(j>0){
			j--;
			dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
		}
		if(j+2<i){
			j+=2;
			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.insert(i);
		it = opt.end();
		it--;
		it--;
		int j1=*it;
		int j2=i;
		int k = (K[j1]==K[j2]) ? 0 : getSplit(K[j1]+1, K[j2], dp[j2]-dp[j1]);
		if(K[j1]==K[j2]) k= (dp[j2] - dp[j1] < 0) ? K[M-1]+1 : K[j2]+1;
		auto it2 = lower_bound(K, K+M, k);
		int l = distance(K, it2);
		pq[l].push({j1,j2});
		if(l<=i) opt.erase(i);
	}
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:71: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]
   71 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:72: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]
   72 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int getSplit(int, int, int)':
teams.cpp:77: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]
   77 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:78: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]
   78 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:104: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]
  104 |    if(pq.size()<K[i]) return 0;
      |       ~~~~~~~~~^~~~~
teams.cpp:151:19: warning: conversion from 'std::iterator_traits<int*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  151 |   int l = distance(K, it2);
      |           ~~~~~~~~^~~~~~~~

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