Submission #44459

#	Time	Username	Problem	Language	Result	Execution time	Memory
44459		Yehezkiel	Svjetlost (COI18_svjetlost)	C++11	100 / 100	2508 ms	163924 KiB

Main

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <iomanip>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define cout if(false)cout
typedef long double LD;
typedef long long LL;
const int MAXN=100000;
const int treesize=2097152;
const LD EPS=(LD) 0.00000000001;
struct point{
	int x,y;
	point(int _x,int _y){
		x=_x;
		y=_y;
	}
	point(){
	}
};
struct vec{
	int x,y;
	vec(int _x,int _y){
		x=_x;
		y=_y;
	}
	vec(){
	}
	LD val(){
		return sqrt((LL) x*x+(LL) y*y);
	}
};
struct segtree{
	LD lazy,maks;
	segtree(){
		lazy=maks=0;
	}
	void update(LD tambah)
	{
		maks+=tambah;
		lazy+=tambah;
	}
};
int n,q,ulang;
set <int> daftar;
vector <int> querylist;
vector <LD> press,ans;
point plist[MAXN+5];

LD Drajat(LD Radian){
	return Radian*180.0/acos(-1.0);
}
LD Radian(LD Drajat){
	return Drajat*acos(-1.0)/180.0;
}
LD sudut(vec v){
	LD ret=atan2(v.y,v.x);
	ret=Drajat(ret);
	if(ret<-EPS)
		ret+=360.0;
	return ret;
}
vec ToVec(point p1,point p2){
	return vec(p2.x-p1.x,p2.y-p1.y);
}
LD jarak(point p1,point p2){
	return ToVec(p1,p2).val();
}

segtree tree[(treesize<<1)+5];
void pushdown(int indeks){
	tree[indeks<<1].update(tree[indeks].lazy);
	tree[(indeks<<1)|1].update(tree[indeks].lazy);
	tree[indeks].lazy=0;
}
void pullup(int indeks){
	assert(fabs(tree[indeks].lazy)<EPS);
	tree[indeks].maks=max(tree[indeks<<1].maks,tree[(indeks<<1)|1].maks);
}
void update(int kiri,int kanan,int indeks,int l,int r,LD tambah){
	if(l<=kiri&&kanan<=r)
	{
		tree[indeks].update(tambah);
		return;
	}
	if(l>kanan||r<kiri)
		return;
	int mid=(kiri+kanan)>>1;
	pushdown(indeks);
	update(kiri,mid,indeks<<1,l,r,tambah);
	update(mid+1,kanan,(indeks<<1)|1,l,r,tambah);
	pullup(indeks);
}
void update(int l,int r,LD tambah){
	cout<<"updating pada tree "<<l<<" "<<r<<" sebanyak "<<tambah<<endl<<endl;
	update(0,(int) press.size()*3-1,1,l,r,tambah);
}
LD dabest(){
	//cout<<"test"<<endl;
	//cout<<"this is dabest "<<tree[1].maks<<endl;
	cout<<"dabest "<<tree[1].maks<<endl<<endl<<endl;
	return tree[1].maks;
}

void compress(){
	for(int i=0;i<5;i++)
		press.pb((LD) 90.0*i);
		
	sort(all(press));
	vector <LD> baru;
	baru.pb(press[0]);
	
	for(int i=1;i<press.size();i++)
	{
		if(!(fabs(baru.back()-press[i])<EPS))
			baru.pb(press[i]);
	}
	press=baru;
}
int nilaipress(LD a){
	int bawah=0,atas=press.size()-1,mid;
	while(bawah<=atas)
	{
		mid=(bawah+atas)>>1;
		if(press[mid]<a-EPS)
			bawah=mid+1;
		else
			atas=mid-1;
	}
	return bawah*3+1;
}

void upd(LD sudutL,LD sudutR,LD val){
	if(ulang==0)
	{
		press.pb(sudutL);
		press.pb(sudutR);
		return;
	}
	
	cout<<"updatenya "<<sudutL<<" "<<sudutR<<" sebanyak "<<val<<endl;
	
	if(sudutR>360.0+EPS)
	{
		cout<<"pecah "<<endl;
		update(nilaipress(sudutL)+1,nilaipress(360.0),val);
		update(nilaipress(0.0),nilaipress(sudutR-360.0)-1,val);
	}
	else
	{
		update(nilaipress(sudutL)+1,nilaipress(sudutR)-1,val);
	}
	
}
void remove(int tadi,int now){
	LD tetha=sudut(ToVec(plist[now],plist[tadi]));
	upd(tetha,tetha+180.0,-jarak(plist[now],plist[tadi]));
}
void add(int tadi,int now){
	//cout<<"add "<<tadi<<" "<<now<<endl;
	LD tetha=sudut(ToVec(plist[now],plist[tadi]));
	upd(tetha,tetha+180.0,jarak(plist[now],plist[tadi]));
}
void enyahkan(int pos){
	if(ulang)
		cout<<"menghapus "<<pos+1<<endl;
	auto it=daftar.find(pos);
	int a,b,c;
	b=pos;
	if(it==daftar.begin())
		a=*prev(daftar.end());
	else
		a=*prev(it);
	
	if(next(it)==daftar.end())
		c=*daftar.begin();
	else
		c=*next(it);
	
	remove(a,b);
	remove(b,c);
	add(a,c);
	daftar.erase(it);
}

void BacaInput(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",&plist[i].x,&plist[i].y);
	scanf("%d",&q);
	querylist.resize(q);
	for(int i=0;i<q;i++)
	{
		scanf("%d",&querylist[i]);
		querylist[i]--;
	}
}
void Solve(){
	for(ulang=0;ulang<2;ulang++)
	{
		//cout<<"pengulangan ke "<<ulang<<endl;
		daftar.clear();
		for(int i=0;i<n;i++)
		{
			daftar.insert(i);
			if(i)
				add(i-1,i);
			else
				add(n-1,i);
		}
		
		if(ulang)		//mau dijawab
			ans.pb(dabest());
		
		for(auto isi:querylist)
		{
			enyahkan(isi);
			if(ulang)		//mau dijawab
				ans.pb(dabest());
		}
		
		if(ulang==0)
			compress();
	}
}
void PrintAll(){
	for(auto isi:ans)
	{
		printf("%.10Lf\n",isi);
	}
}
int main()
{
	//cout<<"membaca input"<<endl;
	BacaInput();
	//cout<<"solving"<<endl;
	Solve();
	//cout<<"printing solution"<<endl;
	PrintAll();
}

Compilation message (stderr)

svjetlost.cpp: In function 'void compress()':
svjetlost.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<press.size();i++)
              ~^~~~~~~~~~~~~
svjetlost.cpp: In function 'void BacaInput()':
svjetlost.cpp:193:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
svjetlost.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&plist[i].x,&plist[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:196:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
svjetlost.cpp:200:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&querylist[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31