Submission #337433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337433	2020-12-20T18:53:03 Z	YJU	Bulldozer (JOI17_bulldozer)	C++14	20 / 100	2000 ms	132180 KB

bulldozer

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<30);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,x[N],y[N],c[N],pos[N],ans,ma[4*N],lma[4*N],rma[4*N],sum[4*N];
vector<ll> lis;
vector<pair<ld,pll> > event;

void mod(ll nda,ll ndb){
	ld cel=asin((y[nda]-y[ndb])/sqrt(SQ(y[nda]-y[ndb])+SQ(x[nda]-x[ndb])));
	cel=(cel+pi/2>2*pi?cel+pi/2-2*pi:cel+pi/2);
	//cout<<nda<<" "<<ndb<<" "<<cel/pi<<"\n";
	event.pb(mp(cel,mp(nda,ndb)));
	cel=(cel+pi>2*pi?cel-pi:cel+pi);
	event.pb(mp(cel,mp(nda,ndb)));
}

void upd(ll id,ll l,ll r,ll to){
	if(l==r-1){ma[id]=lma[id]=rma[id]=max(0LL,c[lis[l]]);sum[id]=c[lis[l]];return ;}
	ll mid=(l+r)>>1;
	if(to<mid)upd(id*2,l,mid,to);
	else upd(id*2+1,mid,r,to);
	sum[id]=sum[id*2]+sum[id*2+1];
	lma[id]=max(lma[id*2],lma[id*2+1]+sum[id*2]);
	rma[id]=max(rma[id*2]+sum[id*2+1],rma[id*2+1]);
	ma[id]=max(max(ma[id*2],ma[id*2+1]),lma[id*2+1]+rma[id*2]);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP(i,n){
		cin>>x[i]>>y[i]>>c[i];
		lis.pb(i);
	}
	sort(lis.begin(),lis.end(),[](ll A,ll B){
		if(x[A]!=x[B])return (x[A]<x[B]);
		return (y[A]>y[B]);
	});
	REP(i,n)pos[lis[i]]=i;
	REP(i,n)upd(1,0,n,i);
	ans=ma[1];
	
	REP(i,n){
		for(int j=i+1;j<n;j++){
			mod(lis[i],lis[j]);
		}
	}
	
	sort(event.begin(),event.end());
	
	//for(auto i:event)cout<<i.Y.X<<" "<<i.Y.Y<<"\n";
	
	REP(i,SZ(event)){
		if(i&&event[i].X!=event[i-1].X)ans=max(ans,ma[1]);
		//cout<<fixed<<setprecision(12)<<event[i].X<<" "<<event[i].Y.X<<" "<<event[i].Y.Y<<"\n";
		//REP(j,n)cout<<lis[j]<<(j==n-1?"\n":" ");
		//cout<<ma[1]<<"\n";
		ll nx=event[i].Y.X,ny=event[i].Y.Y;
		swap(lis[pos[nx]],lis[pos[ny]]);
		upd(1,0,n,pos[nx]);
		upd(1,0,n,pos[ny]);
		swap(pos[nx],pos[ny]);
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1008 KB	Output is correct
2	Correct	5 ms	1008 KB	Output is correct
3	Correct	4 ms	1008 KB	Output is correct
4	Correct	4 ms	1008 KB	Output is correct
5	Incorrect	4 ms	1028 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1008 KB	Output is correct
2	Correct	4 ms	1008 KB	Output is correct
3	Correct	4 ms	1008 KB	Output is correct
4	Correct	4 ms	1136 KB	Output is correct
5	Correct	5 ms	1008 KB	Output is correct
6	Correct	5 ms	1028 KB	Output is correct
7	Correct	4 ms	1028 KB	Output is correct
8	Correct	4 ms	1008 KB	Output is correct
9	Correct	4 ms	1008 KB	Output is correct
10	Correct	5 ms	1008 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	4 ms	1008 KB	Output is correct
22	Correct	4 ms	1008 KB	Output is correct
23	Correct	4 ms	1008 KB	Output is correct
24	Correct	4 ms	1008 KB	Output is correct
25	Correct	4 ms	1008 KB	Output is correct
26	Correct	4 ms	1008 KB	Output is correct
27	Correct	4 ms	1008 KB	Output is correct
28	Correct	4 ms	1008 KB	Output is correct
29	Correct	4 ms	1008 KB	Output is correct
30	Correct	4 ms	1008 KB	Output is correct
31	Correct	4 ms	1008 KB	Output is correct
32	Correct	4 ms	1008 KB	Output is correct

Subtask #3
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1008 KB	Output is correct
2	Correct	4 ms	1008 KB	Output is correct
3	Correct	4 ms	1008 KB	Output is correct
4	Correct	4 ms	1136 KB	Output is correct
5	Correct	5 ms	1008 KB	Output is correct
6	Correct	5 ms	1028 KB	Output is correct
7	Correct	4 ms	1028 KB	Output is correct
8	Correct	4 ms	1008 KB	Output is correct
9	Correct	4 ms	1008 KB	Output is correct
10	Correct	5 ms	1008 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	4 ms	1008 KB	Output is correct
22	Correct	4 ms	1008 KB	Output is correct
23	Correct	4 ms	1008 KB	Output is correct
24	Correct	4 ms	1008 KB	Output is correct
25	Correct	4 ms	1008 KB	Output is correct
26	Correct	4 ms	1008 KB	Output is correct
27	Correct	4 ms	1008 KB	Output is correct
28	Correct	4 ms	1008 KB	Output is correct
29	Correct	4 ms	1008 KB	Output is correct
30	Correct	4 ms	1008 KB	Output is correct
31	Correct	4 ms	1008 KB	Output is correct
32	Correct	4 ms	1008 KB	Output is correct
33	Execution timed out	2087 ms	132180 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1008 KB	Output is correct
2	Correct	4 ms	1008 KB	Output is correct
3	Correct	4 ms	1008 KB	Output is correct
4	Correct	4 ms	1136 KB	Output is correct
5	Correct	5 ms	1008 KB	Output is correct
6	Correct	5 ms	1028 KB	Output is correct
7	Correct	4 ms	1028 KB	Output is correct
8	Correct	4 ms	1008 KB	Output is correct
9	Correct	4 ms	1008 KB	Output is correct
10	Correct	5 ms	1008 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	4 ms	1008 KB	Output is correct
22	Correct	4 ms	1008 KB	Output is correct
23	Correct	4 ms	1008 KB	Output is correct
24	Correct	4 ms	1008 KB	Output is correct
25	Correct	4 ms	1008 KB	Output is correct
26	Correct	4 ms	1008 KB	Output is correct
27	Correct	4 ms	1008 KB	Output is correct
28	Correct	4 ms	1008 KB	Output is correct
29	Correct	4 ms	1008 KB	Output is correct
30	Correct	4 ms	1008 KB	Output is correct
31	Correct	4 ms	1008 KB	Output is correct
32	Correct	4 ms	1008 KB	Output is correct
33	Execution timed out	2087 ms	132180 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1008 KB	Output is correct
2	Correct	5 ms	1008 KB	Output is correct
3	Correct	4 ms	1008 KB	Output is correct
4	Correct	4 ms	1008 KB	Output is correct
5	Incorrect	4 ms	1028 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Submission #337433

Compilation message

Subtask #1 0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0