oj.uz

Submission #44458

# Submission time Handle Problem Language Result Execution time Memory
44458 2018-04-02T08:51:46 Z Yehezkiel Svjetlost (COI18_svjetlost) C++11
100 / 100
 2033 ms 150576 KB 
#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;
//typedef __int128 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 (LD) 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,event;
set <int> daftar;
vector <int> querylist;
vector <LD> ans;
vector <vec> press;
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){
	vec ret;
	ret.x=p2.x-p1.x;
	ret.y=p2.y-p1.y;
	//assert(ret.val()>EPS);
	return ret;
}
LD jarak(point p1,point p2){
	return ToVec(p1,p2).val();
}
int sign(LL angka){
	if(angka>0)
		return 1;
	if(angka<0)
		return -1;
	return 0;
}
LL cross(vec v1,vec v2){
	return (LL) v1.x*v2.y - (LL) v1.y*v2.x;
}
bool cmp(vec v1, vec v2){
	//assert(v1.val()>EPS&&v2.val()>EPS);
	if(sign(v1.y)==sign(v2.y))		//case ++ dan -- dan 00
	{
		if(sign(v1.y))		//case ++ dan --
			return sign(cross(v1,v2))==1;
		else	//case 00
			return sign(v1.x)>sign(v2.x);
	}
	
	if((sign(v1.y)==1&&sign(v2.y)==0)||(sign(v1.y)==0&&sign(v2.y)==1))		//case +0 dan 0+
	{
		if(sign(v1.y)==0)
			return (sign(v1.x)==1);		//kalau positif berarti lebih kecil else lebih besar
		else
			return !(sign(v2.x)==1);
	}
	else	//casae +- , -+ , 0- ,-0
	{
		return sign(v1.y)>sign(v2.y);
	}
}

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;
	//assert(l<=r);
	update(0,event,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(){
	sort(all(press),cmp);
	vector <vec> baru;
	baru.pb(press[0]);
	
	for(int i=1;i<press.size();i++)
	{
		if(cmp(baru.back(),press[i]))
			baru.pb(press[i]);
	}
	press=baru;
	event=3*press.size()-1;
}
int nilaipress(vec v){
	//assert(v.val()>EPS);
	int bawah=0,atas=press.size()-1,mid;
	while(bawah<=atas)
	{
		mid=(bawah+atas)>>1;
		if(cmp(press[mid],v))
			bawah=mid+1;
		else
			atas=mid-1;
	}
	return bawah*3+1;
}

void upd(vec vL,vec vR,LD val){
	if(ulang==0)
	{
		press.pb(vL);
		press.pb(vR);
		return;
	}
	
	int l=nilaipress(vL);
	int r=nilaipress(vR);
		
	if(r<l)	
	{
		cout<<"pecah "<<endl;
		update(l+1,event,val);
		update(0,r-1,val);
	}
	else
	{
		update(l+1,r-1,val);
	}
	
}
void remove(int tadi,int now){
	//assert(tadi!=now);
	vec v1=ToVec(plist[now],plist[tadi]);
	vec v2=ToVec(plist[tadi],plist[now]);
	upd(v1,v2,-jarak(plist[now],plist[tadi]));
}
void add(int tadi,int now){
	//assert(tadi!=now);
	//cout<<"add "<<tadi<<" "<<now<<endl;
	vec v1=ToVec(plist[now],plist[tadi]);
	vec v2=ToVec(plist[tadi],plist[now]);
	upd(v1,v2,jarak(plist[now],plist[tadi]));
}
void enyahkan(int pos){
	auto it=daftar.find(pos);
	//assert(it!=daftar.end());
	//assert(*it==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

svjetlost.cpp: In function 'void compress()':
svjetlost.cpp:155: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:236:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
svjetlost.cpp:238: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:239:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
svjetlost.cpp:243: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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 131704 KB 11 numbers
2 Correct 114 ms 131836 KB 41 numbers
3 Correct 116 ms 131836 KB 11 numbers
4 Correct 115 ms 131856 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 131704 KB 11 numbers
2 Correct 114 ms 131836 KB 41 numbers
3 Correct 116 ms 131836 KB 11 numbers
4 Correct 115 ms 131856 KB 93 numbers
5 Correct 116 ms 131972 KB 101 numbers
6 Correct 125 ms 132252 KB 1201 numbers
7 Correct 131 ms 132252 KB 1556 numbers
8 Correct 136 ms 132348 KB 1996 numbers
9 Correct 136 ms 132348 KB 1960 numbers
10 Correct 138 ms 132348 KB 1991 numbers
11 Correct 144 ms 132376 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 132376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 120 ms 132376 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 145 ms 133164 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 187 ms 134240 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 425 ms 141252 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 420 ms 141252 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 141252 KB 1001 numbers
2 Correct 343 ms 141252 KB 15001 numbers
3 Correct 770 ms 141396 KB 44445 numbers
4 Correct 658 ms 142628 KB 22223 numbers
5 Correct 1444 ms 150280 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 131704 KB 11 numbers
2 Correct 114 ms 131836 KB 41 numbers
3 Correct 116 ms 131836 KB 11 numbers
4 Correct 115 ms 131856 KB 93 numbers
5 Correct 116 ms 131972 KB 101 numbers
6 Correct 125 ms 132252 KB 1201 numbers
7 Correct 131 ms 132252 KB 1556 numbers
8 Correct 136 ms 132348 KB 1996 numbers
9 Correct 136 ms 132348 KB 1960 numbers
10 Correct 138 ms 132348 KB 1991 numbers
11 Correct 144 ms 132376 KB 1963 numbers
12 Correct 121 ms 132376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 120 ms 132376 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 145 ms 133164 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 187 ms 134240 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 425 ms 141252 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 420 ms 141252 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 154 ms 141252 KB 1001 numbers
19 Correct 343 ms 141252 KB 15001 numbers
20 Correct 770 ms 141396 KB 44445 numbers
21 Correct 658 ms 142628 KB 22223 numbers
22 Correct 1444 ms 150280 KB 88889 numbers
23 Correct 2033 ms 150280 KB 98175 numbers
24 Correct 519 ms 150280 KB 25905 numbers
25 Correct 1618 ms 150280 KB 98169 numbers
26 Correct 1634 ms 150280 KB 91845 numbers
27 Correct 1761 ms 150576 KB 98296 numbers
28 Correct 1512 ms 150576 KB 85384 numbers
29 Correct 1416 ms 150576 KB 85317 numbers
30 Correct 1598 ms 150576 KB 98246 numbers
31 Correct 1002 ms 150576 KB 50001 numbers