oj.uz

Submission #44459

# Submission time Handle Problem Language Result Execution time Memory
44459 2018-04-02T08:52:41 Z Yehezkiel Svjetlost (COI18_svjetlost) C++11
100 / 100
 2508 ms 163924 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;
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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 131772 KB 11 numbers
2 Correct 120 ms 131880 KB 41 numbers
3 Correct 122 ms 131880 KB 11 numbers
4 Correct 122 ms 131880 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 131772 KB 11 numbers
2 Correct 120 ms 131880 KB 41 numbers
3 Correct 122 ms 131880 KB 11 numbers
4 Correct 122 ms 131880 KB 93 numbers
5 Correct 127 ms 131904 KB 101 numbers
6 Correct 135 ms 132188 KB 1201 numbers
7 Correct 139 ms 132568 KB 1556 numbers
8 Correct 143 ms 132588 KB 1996 numbers
9 Correct 142 ms 132588 KB 1960 numbers
10 Correct 144 ms 132588 KB 1991 numbers
11 Correct 142 ms 132588 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 132588 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 123 ms 132588 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 159 ms 133660 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 190 ms 135280 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 491 ms 145504 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 482 ms 145504 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 145504 KB 1001 numbers
2 Correct 410 ms 145504 KB 15001 numbers
3 Correct 927 ms 147776 KB 44445 numbers
4 Correct 784 ms 148532 KB 22223 numbers
5 Correct 1816 ms 162616 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 131772 KB 11 numbers
2 Correct 120 ms 131880 KB 41 numbers
3 Correct 122 ms 131880 KB 11 numbers
4 Correct 122 ms 131880 KB 93 numbers
5 Correct 127 ms 131904 KB 101 numbers
6 Correct 135 ms 132188 KB 1201 numbers
7 Correct 139 ms 132568 KB 1556 numbers
8 Correct 143 ms 132588 KB 1996 numbers
9 Correct 142 ms 132588 KB 1960 numbers
10 Correct 144 ms 132588 KB 1991 numbers
11 Correct 142 ms 132588 KB 1963 numbers
12 Correct 115 ms 132588 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 123 ms 132588 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 159 ms 133660 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 190 ms 135280 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 491 ms 145504 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 482 ms 145504 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 131 ms 145504 KB 1001 numbers
19 Correct 410 ms 145504 KB 15001 numbers
20 Correct 927 ms 147776 KB 44445 numbers
21 Correct 784 ms 148532 KB 22223 numbers
22 Correct 1816 ms 162616 KB 88889 numbers
23 Correct 2508 ms 162872 KB 98175 numbers
24 Correct 674 ms 162872 KB 25905 numbers
25 Correct 1953 ms 162872 KB 98169 numbers
26 Correct 1796 ms 162872 KB 91845 numbers
27 Correct 2131 ms 163924 KB 98296 numbers
28 Correct 2020 ms 163924 KB 85384 numbers
29 Correct 1688 ms 163924 KB 85317 numbers
30 Correct 1924 ms 163924 KB 98246 numbers
31 Correct 1151 ms 163924 KB 50001 numbers