oj.uz

Submission #667878

# Submission time Handle Problem Language Result Execution time Memory
667878 2022-12-02T08:28:39 Z Register Svjetlost (COI18_svjetlost) C++14
69 / 100
 602 ms 35216 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-8,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 x,db y){return x<y-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 1 ms 340 KB 11 numbers
2 Correct 1 ms 328 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 324 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 1 ms 328 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 324 KB 93 numbers
5 Correct 1 ms 464 KB 101 numbers
6 Correct 5 ms 844 KB 1201 numbers
7 Correct 6 ms 852 KB 1556 numbers
8 Correct 9 ms 980 KB 1996 numbers
9 Correct 8 ms 1008 KB 1960 numbers
10 Correct 10 ms 980 KB 1991 numbers
11 Correct 8 ms 976 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 3 ms 468 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 13 ms 1984 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 23 ms 3472 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 101 ms 13100 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 112 ms 13108 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 872 KB 1001 numbers
2 Correct 76 ms 7740 KB 15001 numbers
3 Correct 202 ms 17284 KB 44445 numbers
4 Correct 185 ms 15856 KB 22223 numbers
5 Correct 405 ms 33700 KB 88889 numbers

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 1 ms 328 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 324 KB 93 numbers
5 Correct 1 ms 464 KB 101 numbers
6 Correct 5 ms 844 KB 1201 numbers
7 Correct 6 ms 852 KB 1556 numbers
8 Correct 9 ms 980 KB 1996 numbers
9 Correct 8 ms 1008 KB 1960 numbers
10 Correct 10 ms 980 KB 1991 numbers
11 Correct 8 ms 976 KB 1963 numbers
12 Correct 1 ms 340 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 3 ms 468 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 13 ms 1984 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 23 ms 3472 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 101 ms 13100 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 112 ms 13108 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 6 ms 872 KB 1001 numbers
19 Correct 76 ms 7740 KB 15001 numbers
20 Correct 202 ms 17284 KB 44445 numbers
21 Correct 185 ms 15856 KB 22223 numbers
22 Correct 405 ms 33700 KB 88889 numbers
23 Correct 602 ms 35176 KB 98175 numbers
24 Correct 133 ms 9252 KB 25905 numbers
25 Incorrect 490 ms 35216 KB 12020th numbers differ - expected: '3269022120.9973678589', found: '3268980900.5691771507', error = '0.0000126094'
26 Halted 0 ms 0 KB -