oj.uz

Submission #667879

# Submission time Handle Problem Language Result Execution time Memory
667879 2022-12-02T08:30:51 Z Register Svjetlost (COI18_svjetlost) C++14
40 / 100
 420 ms 31164 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-6,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 1 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 0 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 1 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 0 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 7 ms 852 KB 1556 numbers
8 Correct 8 ms 996 KB 1996 numbers
9 Correct 8 ms 980 KB 1960 numbers
10 Correct 12 ms 968 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 0 ms 340 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 468 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 12 ms 1856 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 23 ms 3080 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 99 ms 11320 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 101 ms 11220 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 852 KB 1001 numbers
2 Correct 73 ms 7128 KB 15001 numbers
3 Correct 220 ms 15856 KB 44445 numbers
4 Correct 166 ms 14032 KB 22223 numbers
5 Incorrect 420 ms 31164 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355419636', error = '0.0000123380'
6 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 0 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 7 ms 852 KB 1556 numbers
8 Correct 8 ms 996 KB 1996 numbers
9 Correct 8 ms 980 KB 1960 numbers
10 Correct 12 ms 968 KB 1991 numbers
11 Correct 9 ms 980 KB 1963 numbers
12 Correct 0 ms 340 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 468 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 12 ms 1856 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 23 ms 3080 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 99 ms 11320 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 101 ms 11220 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 6 ms 852 KB 1001 numbers
19 Correct 73 ms 7128 KB 15001 numbers
20 Correct 220 ms 15856 KB 44445 numbers
21 Correct 166 ms 14032 KB 22223 numbers
22 Incorrect 420 ms 31164 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355419636', error = '0.0000123380'
23 Halted 0 ms 0 KB -