IJPC-01

IJPC-01に参加した。

B:silver
問題文読んでqnighyさんだな〜と思う。
座標圧縮+何かかなぁ〜→全部一度に求められる→座標圧縮とかする必要ないなぁ、で満点。
簡単なのにuniqueの亜種っぽいことしてなくてAC状況が気持ち悪いことになってた。(大きいケースになるほどACが増える)

#include"grader.h"
#include"silver.h"
#include"grader.cpp"
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
typedef pair<int,int> pii;
pii maxi[100001];
int beg[100001];
int flag[100000];
void schedule(int day,int tes,int tests[],int ei[])
{
	vector<pii>vec;
	for(int i=0;i<tes;i++)
	{
		vec.push_back(make_pair(max(tests[i]-ei[i]+1,0),-1));
		vec.push_back(make_pair(min(tests[i]+ei[i]-1,day-1),1));
	}
	sort(vec.begin(),vec.end());
	deque<pii>deq;
	for(int p=0;p<vec.size();p++)
	{
		if(vec[p].second==1)
		{
			deq.push_back(vec[p]);
		}
		else
		{
			if(!deq.empty())
			{
				if(deq[deq.size()-1]==make_pair(vec[p].first-1,1))
				{
					deq.pop_back();
				}
				else
				{
					deq.push_back(vec[p]);
				}
			}
			else
			{
				deq.push_back(vec[p]);
			}
		}
	}
	vec.clear();
	for(int r=0;r<deq.size();r++)
	{
		vec.push_back(deq[r]);
	}
	int now=0;
	fill(maxi,maxi+100001,make_pair(-1,-1));
	fill(beg,beg+100001,-1);
	for(int j=0;j<vec.size();j++)
	{
		if(vec[j].second==-1)
		{
			now++;
			beg[now]=vec[j].first;
		}
		else
		{
			if(maxi[now].first<vec[j].first-beg[now])
			{
				maxi[now]=make_pair(vec[j].first-beg[now],beg[now]);
			}
			now--;
		}
	}
	for(int k=1;k<=tes;k++)
	{
		if(maxi[k]==make_pair(-1,-1))
		{
			answer(k,0,0);
		}
		else
		{
			answer(k,maxi[k].second,maxi[k].second+maxi[k].first);
		}
	}
}

A:問題名長い
とりあえず普通にO(n^2)を実装して20点取る。あとは適当にifで分岐させて直線の場合だけとる。45点。
n^2より直線思いつくのに時間かかった(謎)
iterationすぐREでてむずい。

#include"animals.h"
#include"grader.cpp"
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii>pi3;
int par[100000];
vector<int>pat[100000];
vector<int>ko[100000];
set<pii>se;
void dfs(int a)
{
	for(int i=0;i<pat[a].size();i++)
	{
		if(par[pat[a][i]]==-1)
		{
			par[pat[a][i]]=a;
			dfs(pat[a][i]);
			ko[a].push_back(pat[a][i]);
		}
	}
}
int ren(int a)
{
	int sum=0;
	for(int i=0;i<ko[a].size();i++)
	{
		sum+=ren(ko[a][i]);
	}
	sum++;
	return sum;
}
int parent(int a)
{
	for(;;)
	{
		if(par[a]==-2)
		{
			return a;
		}
		a=par[a];
	}
}			
int kaz;
set<pii>mse;
multiset<int>answ;
void init(int num,int edge[][2])
{
	kaz=num;
	if(num<=1000)
	{
	for(int i=0;i<num;i++)
	{
		pat[edge[i][0]].push_back(edge[i][1]);
		pat[edge[i][1]].push_back(edge[i][0]);
	}
	fill(par,par+100000,-1);
	par[0]=-2;
	dfs(0);
	se.insert(make_pair(num,0));/*
	for(int i=0;i<num;i++)
	{
		printf("%d\n",par[i]);
	}*/
	}
	else
	{
		mse.insert(make_pair(0,num-1));
		answ.insert(num);
	}
}
int query(int des)
{
	if(kaz<=1000)
	{
	int pa=parent(des);
	se.erase(make_pair(ren(pa),pa));
	for(int i=0;i<ko[des].size();i++)
	{
		par[ko[des][i]]=-2;
		se.insert(make_pair(ren(ko[des][i]),ko[des][i]));
	}
	ko[des].clear();
	if(par[des]!=-2)
	{
		int hoge=0;
		for(int p=0;p<ko[par[des]].size();p++)
		{
			if(hoge==1)
			{
				ko[par[des]][p-1]=ko[par[des]][p];
			}
			if(ko[par[des]][p]==des)
			{
				hoge=1;
			}
		}
		ko[par[des]].pop_back();
		par[des]=-2;
	}
	se.insert(make_pair(ren(pa),pa));
	set<pii>::iterator it=se.end();
	it--;
	pii ret=*it;/*
	for(int q=0;q<kaz;q++)
	{
		for(int r=0;r<ko[q].size();r++)
		{
			printf("%d ",ko[q][r]);
		}
		printf("\n");
	}*/
	return ret.first;
	}
	else
	{
		set<pii>::iterator ite;
		ite=mse.lower_bound(make_pair(des,10000000));
		ite--;
		pii fuga=*ite;
		multiset<int>::iterator iter=answ.find(fuga.second-fuga.first+1);
		answ.erase(iter);
		answ.insert(des-fuga.first);
		answ.insert(fuga.second-des);
		mse.erase(ite);
		mse.insert(make_pair(fuga.first,des-1));
		mse.insert(make_pair(des+1,fuga.second));
		iter=answ.end();
		iter--;
		int ret=*iter;
		return ret;
	}
}

C:training

適当にやるだけ実装して12点。O(QNlog N)で30点来るらしい。N<=5000だし無理だと思ってた。実装すればよかった。

#include"training.h"
#include"grader.cpp"
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
vector<int>map;
void init(int num,int data[])
{
	for(int i=0;i<num;i++)
	{
		map.push_back(data[i]);
	}
}
void update(int a,int b)
{
	map[a]=b;
}
int train(int a,int b)
{
	int sum=0;
	for(int i=a;i<=b;i++)
	{
		for(int j=i+1;j<=b;j++)
		{
			if(map[i]>map[j])
			{
				sum++;
			}
		}
	}
	return sum;
}