QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#425642	#3276. 出题高手	Hjcc	0	749ms	29788kb	C++14	1.6kb	2024-05-30 15:12:21	2024-05-30 15:12:23

Judging History

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

[2024-05-30 15:12:23]
评测

测评结果：0
用时：749ms
内存：29788kb

查看

[2024-05-30 15:12:21]
提交

answer

# include <bits/stdc++.h>
# define ll long long

using namespace std;

const int N = 1e5 + 5, K = 50;

struct Fr {
ll a, b;
}st[20][N];

ll s[N], sum[N];
int n, m;

bool operator <(Fr x, Fr y) {
  return x.a * y.b < y.a * x.b;
}

Fr clc(int l, int r) {
  // cerr << l << ' ' << r << ' ' << (sum[r] - sum[l - 1]) * (sum[r] - sum[l - 1]) << '\n';
  return (Fr){(sum[r] - sum[l - 1]) * (sum[r] - sum[l - 1]), r - l + 1};
}

void init() {
  for (int i = 1; i <= n - K + 1; i++) {
    Fr mx = {0, 1};
    for (int j = i; j < i + K; j++) {
      mx = max(mx, clc(i, j));
    }
    st[0][i] = mx;
  }
  for (int j = 1; j < 20; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << j >> 1)]);
    }
  }
}

Fr query(int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return max(st[k][l], st[k][r - (1 << k) + 1]);
}

Fr pr(int l, int r) {
  Fr res = {0, 1};
  if (r - l + 1 >= K) {
    res = query(l, r - K + 1);
  }
  for (int i = max(l, r - K + 2); i <= r; i++) {
    for (int j = i; j <= r; j++) {
      res = max(res, clc(i, j));
    }
  }
  ll g = __gcd(res.a, res.b);
  res.a /= g, res.b /= g;
  return res;
}

int main() {
# ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
# endif
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s[i], sum[i] = sum[i - 1] + s[i];
  }
  init();
  cin >> m;
  while (m--) {
    int l, r; cin >> l >> r;
    Fr ans = pr(l, r);
    cout << ans.a << ' ' << ans.b << '\n';
  }
  return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 200ms

memory: 4012kb

input:

2000
-113 314 -664 697 211 -199 -38 -190 8 -661 910 -811 -113 942 77 433 -261 -368 129 -525 968 -608 -21 38 -562 438 -935 -228 220 333 985 -430 916 586 764 476 794 664 383 503 206 -60 380 -130 -988 -904 -996 -304 -286 31 114 119 850 -942 714 -369 -842 250 -192 -462 -727 -427 -602 126 231 718 121 559...

output:

54826875 11
14638276 7
1185921 1
81018001 24
6310144 3
12545764 5
3362000 1
23068809 8
23068809 8
12545764 5
1444908 1
5424241 3
1083603 1
2140369 1
2752281 2
3095072 1
3003289 2
4959529 2
17106496 13
4780232 1
89605156 31
8543929 4
129163225 48
5094049 2
68591524 23
8543929 4
35688676 11
3775249 1
...

result:

wrong answer 61st numbers differ - expected: '372683025', found: '3775249'

Subtask #2:

score: 0

Wrong Answer

Test #6:

score: 0

Wrong Answer

time: 26ms

memory: 29788kb

input:

100000
754 792 -680 426 425 347 481 -690 530 378 73 -907 -431 45 -530 -552 440 -890 -15 712 695 -679 -310 13 718 805 193 -291 -877 -74 -355 511 -679 -395 166 -710 -657 -19 874 26 832 507 854 -289 700 -404 472 -302 -977 8 -698 40 766 705 369 838 700 -964 552 -535 -75 -608 -181 -503 468 447 772 904 -2...

output:

136866601 21

result:

wrong answer 1st numbers differ - expected: '466344025', found: '136866601'

Subtask #3:

score: 0

Runtime Error

Test #11:

score: 0

Runtime Error

input:

500000
794 -75 -596 -322 -945 -908 -609 -164 488 626 -877 -710 140 -120 -475 -837 738 669 634 -643 -682 667 816 -785 -608 -836 -860 -932 242 70 -620 268 -121 288 209 -392 732 750 558 -480 565 327 -217 -891 767 211 -690 -66 813 -889 952 615 432 19 411 800 678 718 522 422 940 -510 -544 449 -357 640 40...

output:

result:

Subtask #4:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 23ms

memory: 29788kb

input:

100000
-496 -233 354 -632 -196 177 -878 -255 -19 -636 685 -70 101 -975 -406 -988 -965 -205 563 -766 763 511 -116 -746 -129 14 106 928 -457 -257 -283 226 3 899 -359 -792 615 490 -57 986 -243 624 -239 931 -555 -821 -72 -611 -380 -397 248 -132 956 -195 -322 -231 319 -214 837 -379 -931 -301 -4 -673 280 ...

output:

131576642 21
13957947 4
67914081 16
33243858 7
10885778 3
27836176 7
50680161 11
52128400 17
106770889 25
2411809 2
2835045 1
14017536 5
134699236 43
100841764 27
28100601 11
17546888 5
23396569 6
21762225 7
4012009 3
2661336 1
42947912 11
3474284 1
61496964 19
3672245 1
6120676 3
7573504 3
14891881...

result:

wrong answer 1st numbers differ - expected: '1352474176', found: '131576642'

Subtask #5:

score: 0

Wrong Answer

Test #31:

score: 0

Wrong Answer

time: 749ms

memory: 29728kb

input:

100000
139 -485 -497 -818 254 169 -560 22 377 -67 -243 -75 743 -788 -676 -26 -775 371 576 -303 54 733 422 800 445 687 479 -16 -288 259 783 -586 912 616 439 -416 676 -555 172 659 501 -868 337 22 -60 260 603 -982 -149 466 769 -595 -117 949 -544 904 753 20 776 175 -888 937 -792 -647 -615 59 -298 452 -6...

output:

165868641 25
3916125 1
4343056 1
23049601 8
19713600 7
62900761 15
46076944 15
6620329 2
3775805 1
7868025 4
20659592 7
66569281 16
3354050 1
48818169 10
16370116 5
44129449 10
62837329 19
10975969 2
2958400 1
6786025 2
2683044 1
3323047 1
83631025 17
10329796 3
78198649 18
7840000 3
6240000 1
65076...

result:

wrong answer 1st numbers differ - expected: '401594700', found: '165868641'