Submission #667881

#	Time	Username	Problem	Language	Result	Execution time	Memory
667881		Register	Svjetlost (COI18_svjetlost)	C++14	100 / 100	611 ms	35332 KiB

Main

#include <bits/stdc++.h>
#define lc pos<<1
#define rc pos<<1|1
using namespace std;
using db=long double;
const int N=1e5+5,M=(1<<20)+5;
const db eps=1e-11,pi=acos(-1);
int n,q,pre[N],nxt[N];
db mx[M],tg[M];
vector<db> v;
struct vec{
	int x,y;
	void read() {scanf("%d%d",&x,&y);}
}p[N];
using cv=const vec&;
vec operator - (cv t1,cv t2) {return {t1.x-t2.x,t1.y-t2.y};}
db len(cv t) {return hypot(t.x,t.y);}
db ang(cv t) {return atan2(t.y,t.x);}
struct sb{
	db a,l;
	void init(cv t) {a=ang(t);l=len(t);}
}dl1[N],dl2[N],ad[N];
void upd(int l,int r,int pos,int L,int R,db x){
	if(L>R) return;
	if(L<=l&&r<=R) {mx[pos]+=x;tg[pos]+=x;return;}
	int mid=l+r>>1;
	if(L<=mid) upd(l,mid,lc,L,R,x);
	if(R>mid) upd(mid+1,r,rc,L,R,x);
	mx[pos]=max(mx[lc],mx[rc])+tg[pos];
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) p[i].read(),nxt[i]=(i+1)%n,pre[i]=(i+n-1)%n;
	for(int i=0;i<n;i++) v.push_back(ang(p[(i+1)%n]-p[i]));
	scanf("%d",&q);
	for(int i=0,x;i<q;i++)
		scanf("%d",&x),x--,
		dl1[i].init(p[x]-p[pre[x]]),
		dl2[i].init(p[nxt[x]]-p[x]),
		ad[i].init(p[nxt[x]]-p[pre[x]]),
		v.push_back(ad[i].a),
		nxt[pre[x]]=nxt[x],
		pre[nxt[x]]=pre[x];
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end(),[](db x,db y){return fabs(x-y)<=eps;}),v.end());
	int m=v.size();
	auto pos=[&](db x) {return lower_bound(v.begin(),v.end(),x,[](db a,db b){return a<b-eps;})-v.begin();};
	auto add=[&](db x,db y){
		int t=pos(x)+1;
		if((x+=pi)>v.back()+eps) upd(1,m,1,t,m,y),t=1,x-=pi*2;
		upd(1,m,1,t,pos(x),y);
	};
	for(int i=0;i<n;i++) add(ang(p[(i+1)%n]-p[i]),len(p[(i+1)%n]-p[i]));
	printf("%.6Lf\n",mx[1]);
	for(int i=0;i<q;i++)
		add(dl1[i].a,-dl1[i].l),
		add(dl2[i].a,-dl2[i].l),
		add(ad[i].a,ad[i].l),
		printf("%.6Lf\n",mx[1]);
	return 0;
}

Compilation message (stderr)

svjetlost.cpp: In function 'void upd(int, int, int, int, int, db)':
svjetlost.cpp:26:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  int mid=l+r>>1;
      |          ~^~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
svjetlost.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
svjetlost.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d",&x),x--,
      |   ~~~~~^~~~~~~~~
svjetlost.cpp: In member function 'void vec::read()':
svjetlost.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  void read() {scanf("%d%d",&x,&y);}
      |               ~~~~~^~~~~~~~~~~~~~

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