QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564886 | #1880. Nikanor Loves Games | xzf_200906 | WA | 1ms | 7800kb | C++14 | 1.7kb | 2024-09-15 16:34:09 | 2024-09-15 16:34:10 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
using namespace std;
struct Event{
int x,val;
bool operator<(Event e){
return x<e.x;
}
}event[1000000];
struct Line{
LL k,b;
LL operator()(int x){
return 1ll*k*x+b;
}
}tree[1000000];
int ls[1000000],rs[1000000],tot=1;
void change(int p,int l,int r,Line line){
if(tree[p](l)>=line(l)&&tree[p](r)>=line(r)) return;
if(tree[p](l)<=line(l)&&tree[p](r)<=line(r)){
tree[p]=line;
return;
}
int mid=(l+r)>>1;
if(ls[p]==0){
ls[p]=++tot;
tree[tot].b=-1000000000000ll;
}
change(ls[p],l,mid,line);
if(rs[p]==0){
rs[p]=++tot;
tree[tot].b=-1000000000000ll;
}
change(rs[p],mid+1,r,line);
}
LL query(int p,int l,int r,int pos){
if(p==0) return -1000000000000ll;
int mid=(l+r)>>1;
LL val=tree[p](pos);
if(pos<=mid) return max(query(ls[p],l,mid,pos),val);
else return max(query(rs[p],mid+1,r,pos),val);
}
Line li[1000000];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tree[1].b=-1000000000000ll;
int n;
cin>>n;
LL shift=0;
for(int i=1;i<=n;i++){
int a,b,x;
cin>>a>>b>>x;
shift-=x*4ll;
x*=2;
event[i*2-1]={a,x};
event[i*2]={b,x};
}
sort(event+1,event+n*2+1);
LL sum=0,ans=0;
for(int i=1;i<=n*2;i++){
sum+=event[i].val;
li[i]={-4ll*event[i].x,sum};
//change(1,1,1000000000,{-4ll*event[i].x,sum});
}
sum=0;
for(int i=1;i<=n*2;i++){
sum+=event[i].val;
for(int j=1;j<=n*2;j++) ans=max(ans,sum+li[j](event[i].x));
//ans=max(ans,sum+query(1,1,1000000000,event[i].x));
}
ans+=shift;
if(ans<0){
cout<<'-';
ans=-ans;
}
cout<<(ans>>2)<<'.';
if((ans&3)==0) cout<<"00\n";
if((ans&3)==1) cout<<"25\n";
if((ans&3)==2) cout<<"50\n";
if((ans&3)==3) cout<<"75\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7756kb
input:
2 1 4 15 3 5 10
output:
2.50
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7720kb
input:
1 2 2 8
output:
4.00
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7800kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.00
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
2 14 68 12 28 2 46
output:
-16.00
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.50
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.50
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.50
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7752kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9.00
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 7688kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6.00
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7676kb
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:
32.00
result:
ok found '32.0000000', expected '32.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7764kb
input:
10 6 5 10 10 15 21 7 2 30 14 6 12 1 11 6 1 13 19 8 13 29 9 4 14 1 4 29 4 12 17
output:
12.00
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
10 5 15 15 3 14 20 11 14 26 15 12 22 5 15 11 12 10 10 1 12 18 7 7 14 3 5 10 12 9 23
output:
-6.00
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
10 3 9 29 9 5 27 14 13 21 3 15 15 14 11 24 9 14 22 9 3 20 12 15 27 5 13 21 13 11 14
output:
-5.00
result:
ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 7692kb
input:
10 3 13 11 3 5 20 9 10 1 5 5 25 10 1 29 6 10 26 1 15 1 10 10 18 6 6 2 14 6 20
output:
21.00
result:
ok found '21.0000000', expected '21.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
100 68 91 90 56 38 71 69 57 87 80 62 21 31 80 25 36 48 40 71 66 49 15 57 78 96 69 43 25 73 57 86 13 5 23 98 18 83 94 9 8 22 43 46 3 50 81 11 26 14 35 39 49 68 73 41 11 25 35 47 48 5 96 15 15 56 60 42 1 40 11 4 25 57 72 9 43 3 90 16 45 36 83 50 17 55 40 39 72 37 6 70 84 24 12 36 95 43 15 13 82 28 68 ...
output:
35.50
result:
ok found '35.5000000', expected '35.5000000', error '0.0000000'
Test #16:
score: -100
Wrong Answer
time: 1ms
memory: 7676kb
input:
100 92 35 39 34 92 36 45 45 46 66 5 64 22 21 48 53 70 91 93 19 98 97 67 54 57 77 64 90 81 23 12 83 92 59 3 26 13 65 47 19 23 58 27 58 38 60 18 70 32 94 53 100 66 97 33 53 16 56 2 64 8 9 55 93 92 22 27 25 39 45 49 24 76 80 89 73 55 77 69 53 90 39 77 40 86 12 11 23 87 25 8 96 31 73 45 98 52 62 55 98 9...
output:
-168.00
result:
wrong answer 1st numbers differ - expected: '-100.0000000', found: '-168.0000000', error = '0.6800000'