QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111927#1880. Nikanor Loves GameslingchenWA 28ms7604kbC++142.0kb2023-06-09 10:20:492023-06-09 10:20:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 10:20:50]
  • 评测
  • 测评结果：WA
  • 用时：28ms
  • 内存：7604kb
查看
  • [2023-06-09 10:20:49]
  • 提交

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[pmid]-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<<mid<<" "<<pmid<<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?
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3676kb

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: 3680kb

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: 3600kb

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: 3564kb

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: 3552kb

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: 1ms
memory: 3668kb

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: 3512kb

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: 2ms
memory: 3524kb

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: 3676kb

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: 0
Accepted
time: 2ms
memory: 3604kb

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

result:

ok found '32.0000000', expected '32.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3508kb

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

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3564kb

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

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3556kb

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

result:

ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3680kb

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

result:

ok found '21.0000000', expected '21.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3564kb

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.5

result:

ok found '35.5000000', expected '35.5000000', error '0.0000000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3508kb

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:

-100

result:

ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

100
20 84 93
15 45 13
28 33 2
49 41 12
12 50 59
62 89 49
11 60 42
74 84 33
14 94 85
51 2 89
26 66 87
92 12 26
47 32 84
34 16 80
20 16 27
48 34 14
54 61 66
52 47 21
41 87 3
81 45 68
24 18 94
71 23 87
12 49 34
79 6 6
91 92 56
3 15 64
22 69 41
91 3 60
21 76 79
65 41 48
46 9 35
34 54 92
68 10 1
22 82 17...

output:

25.5

result:

ok found '25.5000000', expected '25.5000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3532kb

input:

100
44 28 47
89 7 89
7 21 57
27 92 56
14 96 86
79 11 7
29 4 95
56 93 16
71 2 6
100 14 59
53 32 82
24 20 35
73 7 22
44 9 91
5 70 24
31 41 50
72 19 80
100 44 46
33 26 94
2 4 72
27 35 29
49 54 44
92 73 33
13 55 92
6 3 31
37 76 47
75 77 87
44 33 80
63 48 51
12 90 66
83 17 46
99 59 78
76 61 35
39 52 91
9...

output:

-57

result:

ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100
68 73 96
63 60 58
86 13 29
13 32 95
4 25 97
96 30 61
55 57 43
34 98 95
32 14 27
65 26 38
79 10 69
56 33 35
98 82 59
55 9 5
82 25 12
19 53 94
90 82 6
48 29 70
29 60 76
23 59 89
38 44 64
31 81 10
77 96 24
51 99 79
25 19 11
68 32 34
28 89 38
100 64 4
94 16 19
58 40 89
17 34 57
64 69 80
92 12 81
63 ...

output:

-81.5

result:

ok found '-81.5000000', expected '-81.5000000', error '-0.0000000'

Test #20:

score: -100
Wrong Answer
time: 28ms
memory: 7604kb

input:

200000
14 11 10
2 6 10
18 13 7
8 5 11
13 5 14
16 14 2
4 5 17
4 20 7
7 3 9
9 8 11
15 1 20
19 13 3
19 17 15
9 16 20
5 5 15
2 1 6
11 14 13
8 13 7
2 3 10
7 18 9
1 4 12
17 3 7
14 4 17
12 14 11
18 11 6
11 7 15
10 4 13
13 2 14
2 1 18
7 3 18
12 16 19
17 13 7
7 17 1
20 9 2
2 1 2
6 13 11
7 11 9
20 16 3
9 4 4
...

output:

2.10086e+06

result:

wrong answer 1st numbers differ - expected: '2100856.0000000', found: '2100860.0000000', error = '0.0000019'
English 繁體中文 简体中文

Server Time: 2025-01-21 00:58:01 | OpenSource Project