oj.uz

Submission #793780

# Submission time Handle Problem Language Result Execution time Memory
793780 2023-07-26T06:41:50 Z 이성호(#10059) Triangle Collection (CCO23_day2problem3) C++17
10 / 25
 4000 ms 8100 KB 
#include <iostream>
#define int long long
using namespace std;
const int inf = 1e18;

int N;
int c[200005];
int lft[200005];
int made[200005];
int prf[200005], prf2[200005];
int calc()
{
    int l = 0, r = inf;
    while (l < r) {
        fill(made, made + N + 1, 0);
        for (int i = 1; i <= N; i++) lft[i] = c[i];
        int m = l + r + 1 >> 1; //m ���� �� �ִ°�?
        int req = m;
        for (int i = N; i >= 1; i--) {
            if (c[i] / 2 <= req) {
                made[i] = c[i] / 2;
                req -= c[i] / 2;
                lft[i] %= 2;
            }
            else {
                made[i] = req;
                lft[i] -= req * 2;
                req = 0;
                break;
            }
        }
        if (req) {
            r = m - 1;
            continue;
        }
        bool ok = true;
        for (int i = 1; i <= N; i++) prf[i] = prf[i-1] + lft[i];
        for (int i = 1; i <= N; i++) prf2[i] = prf2[i-1] + made[i];
        for (int i = 1; i <= N; i++) {
            ok &= prf[min(N, 2 * i - 1)] >= prf2[i];
        }
        if (!ok) r = m - 1;
        else l = m;
    }
    return l;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) cin >> c[i];
    while (Q--) {
        int l, d; cin >> l >> d; c[l] += d;
        cout << calc() << '\n';
    }
}

Compilation message

Main.cpp: In function 'long long int calc()':
Main.cpp:17:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         int m = l + r + 1 >> 1; //m   ִ°?
      |                 ~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 14 ms 364 KB Output is correct
6 Correct 555 ms 412 KB Output is correct
7 Correct 544 ms 408 KB Output is correct
8 Correct 272 ms 380 KB Output is correct
9 Correct 551 ms 412 KB Output is correct
10 Correct 504 ms 540 KB Output is correct
11 Correct 499 ms 340 KB Output is correct
12 Correct 496 ms 412 KB Output is correct
13 Correct 443 ms 420 KB Output is correct
14 Correct 211 ms 372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 14 ms 364 KB Output is correct
6 Correct 555 ms 412 KB Output is correct
7 Correct 544 ms 408 KB Output is correct
8 Correct 272 ms 380 KB Output is correct
9 Correct 551 ms 412 KB Output is correct
10 Correct 504 ms 540 KB Output is correct
11 Correct 499 ms 340 KB Output is correct
12 Correct 496 ms 412 KB Output is correct
13 Correct 443 ms 420 KB Output is correct
14 Correct 211 ms 372 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1206 ms 428 KB Output is correct
18 Correct 1203 ms 432 KB Output is correct
19 Correct 1201 ms 552 KB Output is correct
20 Correct 1232 ms 436 KB Output is correct
21 Correct 623 ms 416 KB Output is correct
22 Correct 1235 ms 440 KB Output is correct
23 Correct 784 ms 424 KB Output is correct
24 Correct 741 ms 432 KB Output is correct
25 Correct 1222 ms 552 KB Output is correct
26 Correct 629 ms 428 KB Output is correct
27 Correct 496 ms 412 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 416 KB Output is correct
2 Correct 498 ms 416 KB Output is correct
3 Correct 256 ms 728 KB Output is correct
4 Execution timed out 4035 ms 8100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 340 KB Output is correct
2 Correct 1223 ms 440 KB Output is correct
3 Correct 1219 ms 456 KB Output is correct
4 Correct 612 ms 416 KB Output is correct
5 Execution timed out 4040 ms 8012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 14 ms 364 KB Output is correct
6 Correct 555 ms 412 KB Output is correct
7 Correct 544 ms 408 KB Output is correct
8 Correct 272 ms 380 KB Output is correct
9 Correct 551 ms 412 KB Output is correct
10 Correct 504 ms 540 KB Output is correct
11 Correct 499 ms 340 KB Output is correct
12 Correct 496 ms 412 KB Output is correct
13 Correct 443 ms 420 KB Output is correct
14 Correct 211 ms 372 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1206 ms 428 KB Output is correct
18 Correct 1203 ms 432 KB Output is correct
19 Correct 1201 ms 552 KB Output is correct
20 Correct 1232 ms 436 KB Output is correct
21 Correct 623 ms 416 KB Output is correct
22 Correct 1235 ms 440 KB Output is correct
23 Correct 784 ms 424 KB Output is correct
24 Correct 741 ms 432 KB Output is correct
25 Correct 1222 ms 552 KB Output is correct
26 Correct 629 ms 428 KB Output is correct
27 Correct 496 ms 412 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 532 ms 416 KB Output is correct
30 Correct 498 ms 416 KB Output is correct
31 Correct 256 ms 728 KB Output is correct
32 Execution timed out 4035 ms 8100 KB Time limit exceeded
33 Halted 0 ms 0 KB -