oj.uz

Submission #667881

# Submission time Handle Problem Language Result Execution time Memory
667881 2022-12-02T08:32:44 Z Register Svjetlost (COI18_svjetlost) C++14
100 / 100
 611 ms 35332 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 2 ms 468 KB 101 numbers
6 Correct 5 ms 852 KB 1201 numbers
7 Correct 6 ms 852 KB 1556 numbers
8 Correct 8 ms 980 KB 1996 numbers
9 Correct 9 ms 980 KB 1960 numbers
10 Correct 8 ms 988 KB 1991 numbers
11 Correct 9 ms 980 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 560 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 12 ms 1744 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 22 ms 3120 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 99 ms 11356 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 98 ms 11316 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB 1001 numbers
2 Correct 74 ms 7160 KB 15001 numbers
3 Correct 209 ms 15872 KB 44445 numbers
4 Correct 165 ms 14068 KB 22223 numbers
5 Correct 409 ms 31152 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 2 ms 468 KB 101 numbers
6 Correct 5 ms 852 KB 1201 numbers
7 Correct 6 ms 852 KB 1556 numbers
8 Correct 8 ms 980 KB 1996 numbers
9 Correct 9 ms 980 KB 1960 numbers
10 Correct 8 ms 988 KB 1991 numbers
11 Correct 9 ms 980 KB 1963 numbers
12 Correct 1 ms 340 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 560 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 12 ms 1744 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 22 ms 3120 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 99 ms 11356 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 98 ms 11316 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 5 ms 852 KB 1001 numbers
19 Correct 74 ms 7160 KB 15001 numbers
20 Correct 209 ms 15872 KB 44445 numbers
21 Correct 165 ms 14068 KB 22223 numbers
22 Correct 409 ms 31152 KB 88889 numbers
23 Correct 611 ms 32456 KB 98175 numbers
24 Correct 133 ms 8708 KB 25905 numbers
25 Correct 473 ms 32448 KB 98169 numbers
26 Correct 437 ms 31428 KB 91845 numbers
27 Correct 486 ms 35332 KB 98296 numbers
28 Correct 439 ms 32856 KB 85384 numbers
29 Correct 416 ms 32760 KB 85317 numbers
30 Correct 474 ms 35192 KB 98246 numbers
31 Correct 252 ms 19484 KB 50001 numbers