QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #111923 | #1880. Nikanor Loves Games | lingchen | WA | 2ms | 5728kb | C++14 | 2.0kb | 2023-06-09 10:13:01 | 2023-06-09 10:13:04 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,t) for(int i=s,__=t;i<=__;i++)
#define pre(i,s,t) for(int i=s,__=t;i>=__;i--)
#define ll long long
#define fi first
#define se second
#define ls (k<<1)
#define rs (k<<1|1)
#define mkp make_pair
#define pii pair<int,int>
#define p_b push_back
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
const int N=1e6+10,mod=998244353;
using namespace std;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
int T,n,a[N],b[N],w[N],p[N],cnt;
int k;
ll s[N],ans=-1e18;
inline void solve(int l,int r,int pl,int pr){
if(l>r)return;
int mid=l+r>>1,pmid=pl;
rep(i,pl+1,pr)
if(s[pl]-4ll*p[mid]*p[pmid]<s[i]-4ll*p[mid]*p[i])pmid=i;
ans=max(ans,s[mid]+s[pmid]-4ll*p[mid]*p[pmid]);
// cout<<ans<<endl;
solve(l,mid-1,pmid,pr);solve(mid+1,r,pl,pmid);
}
int main() {
// freopen("data3.in","r",stdin);
//freopen("test.out","w",stdout);
cin>>n;p[++cnt]=1;
rep(i,1,n)a[i]=read(),b[i]=read(),w[i]=read(),p[++cnt]=a[i],p[++cnt]=b[i];
sort(p+1,p+cnt+1);
cnt=unique(p+1,p+cnt+1)-p-1;
rep(i,1,n){
a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
b[i]=lower_bound(p+1,p+cnt+1,b[i])-p;
s[0]-=2*w[i];
s[a[i]]+=2*w[i],s[b[i]]+=2*w[i];
}
rep(i,1,cnt)s[i]+=s[i-1];
solve(1,cnt,1,cnt);
cout<<(double)ans/4<<endl;
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Interger overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5716kb
input:
2 1 4 15 3 5 10
output:
2.5
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5604kb
input:
1 2 2 8
output:
4
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5604kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5636kb
input:
2 14 68 12 28 2 46
output:
-16
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5728kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.5
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5600kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.5
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5568kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.5
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 5720kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 5548kb
input:
10 8 10 26 11 2 28 13 4 13 11 1 26 6 15 23 12 8 7 9 8 11 11 10 17 8 11 18 3 10 27
output:
9.5
result:
wrong answer 1st numbers differ - expected: '32.0000000', found: '9.5000000', error = '0.7031250'