oj.uz

Submission #44457

# Submission time Handle Problem Language Result Execution time Memory
44457 2018-04-02T08:43:31 Z Yehezkiel Svjetlost (COI18_svjetlost) C++11
100 / 100
 1962 ms 150584 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=1048576;
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<<2)+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 115 ms 131704 KB 11 numbers
2 Correct 116 ms 131704 KB 41 numbers
3 Correct 119 ms 131892 KB 11 numbers
4 Correct 119 ms 131968 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 131704 KB 11 numbers
2 Correct 116 ms 131704 KB 41 numbers
3 Correct 119 ms 131892 KB 11 numbers
4 Correct 119 ms 131968 KB 93 numbers
5 Correct 116 ms 131968 KB 101 numbers
6 Correct 126 ms 132120 KB 1201 numbers
7 Correct 133 ms 132120 KB 1556 numbers
8 Correct 137 ms 132280 KB 1996 numbers
9 Correct 137 ms 132332 KB 1960 numbers
10 Correct 141 ms 132340 KB 1991 numbers
11 Correct 134 ms 132340 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 132340 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 116 ms 132340 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 148 ms 133096 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 179 ms 134304 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 424 ms 141020 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 423 ms 141040 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 141040 KB 1001 numbers
2 Correct 337 ms 141040 KB 15001 numbers
3 Correct 742 ms 141476 KB 44445 numbers
4 Correct 642 ms 142440 KB 22223 numbers
5 Correct 1407 ms 150112 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 131704 KB 11 numbers
2 Correct 116 ms 131704 KB 41 numbers
3 Correct 119 ms 131892 KB 11 numbers
4 Correct 119 ms 131968 KB 93 numbers
5 Correct 116 ms 131968 KB 101 numbers
6 Correct 126 ms 132120 KB 1201 numbers
7 Correct 133 ms 132120 KB 1556 numbers
8 Correct 137 ms 132280 KB 1996 numbers
9 Correct 137 ms 132332 KB 1960 numbers
10 Correct 141 ms 132340 KB 1991 numbers
11 Correct 134 ms 132340 KB 1963 numbers
12 Correct 116 ms 132340 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 116 ms 132340 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 148 ms 133096 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 179 ms 134304 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 424 ms 141020 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 423 ms 141040 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 127 ms 141040 KB 1001 numbers
19 Correct 337 ms 141040 KB 15001 numbers
20 Correct 742 ms 141476 KB 44445 numbers
21 Correct 642 ms 142440 KB 22223 numbers
22 Correct 1407 ms 150112 KB 88889 numbers
23 Correct 1962 ms 150112 KB 98175 numbers
24 Correct 528 ms 150112 KB 25905 numbers
25 Correct 1574 ms 150112 KB 98169 numbers
26 Correct 1469 ms 150112 KB 91845 numbers
27 Correct 1589 ms 150584 KB 98296 numbers
28 Correct 1496 ms 150584 KB 85384 numbers
29 Correct 1399 ms 150584 KB 85317 numbers
30 Correct 1560 ms 150584 KB 98246 numbers
31 Correct 905 ms 150584 KB 50001 numbers