oj.uz

Submission #431096

# Submission time Handle Problem Language Result Execution time Memory
431096 2021-06-17T09:30:26 Z Hideo Food Court (JOI21_foodcourt) C++17
2 / 100
 1000 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define pi pair < int, int >

const int N = 65007;
const int INF = 1e9 + 7;

ll cnt[N];
int n, m, q;

deque < pair < ll , pi > > dq[N];

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++){
        int t;
        cin >> t;
        if (t == 1){
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            for (int j = l; j <= r; j++){
                dq[j].pb({cnt[j], {k, c}});
                cnt[j] += k;
            }
        }
        else if (t == 2){
            int l, r, k;
            cin >> l >> r >> k;
            for (int j = l; j <= r; j++){
                int kc = k;
                while (!dq[j].empty() && kc){
                    int a = dq[j].front().sc.fr, b = dq[j].front().sc.sc, cc = dq[j].front().fr;
                    dq[j].pop_front();
                    if (a > kc){
                        dq[j].push_front({cc + kc, {a - kc, b}});
                        break;
                    }
                    kc -= a;
                }
            }
        }
        else {
            int a;
            ll b;
            cin >> a >> b;
            if (dq[a].empty()){
                cout << 0 << endl;
                continue;
            }
            b += dq[a].front().fr;
            if (dq[a].back().fr + 1ll * dq[a].back().sc.fr < b){
                cout << 0 << endl;
                continue;
            }
            int l = 0, r = dq[a].size();
            while (l + 1 < r){
                int mid = (l + r) >> 1;
                if (dq[a][mid].fr < b)
                    l = mid;
                else
                    r = mid;
            }

            cout << dq[a][l].sc.sc << endl;
        }
    }
}

Compilation message

foodcourt.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main (){
      | ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44484 KB Output is correct
2 Correct 46 ms 44896 KB Output is correct
3 Correct 52 ms 51424 KB Output is correct
4 Correct 63 ms 54992 KB Output is correct
5 Correct 33 ms 44028 KB Output is correct
6 Correct 34 ms 44060 KB Output is correct
7 Correct 62 ms 56612 KB Output is correct
8 Correct 60 ms 52188 KB Output is correct
9 Correct 59 ms 45000 KB Output is correct
10 Correct 70 ms 51780 KB Output is correct
11 Correct 55 ms 48732 KB Output is correct
12 Correct 51 ms 44932 KB Output is correct
13 Correct 51 ms 45032 KB Output is correct
14 Correct 61 ms 46116 KB Output is correct
15 Correct 51 ms 47056 KB Output is correct
16 Correct 54 ms 46128 KB Output is correct
17 Correct 49 ms 44364 KB Output is correct
18 Correct 49 ms 44544 KB Output is correct
19 Correct 33 ms 44000 KB Output is correct
20 Correct 35 ms 44024 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44484 KB Output is correct
2 Correct 46 ms 44896 KB Output is correct
3 Correct 52 ms 51424 KB Output is correct
4 Correct 63 ms 54992 KB Output is correct
5 Correct 33 ms 44028 KB Output is correct
6 Correct 34 ms 44060 KB Output is correct
7 Correct 62 ms 56612 KB Output is correct
8 Correct 60 ms 52188 KB Output is correct
9 Correct 59 ms 45000 KB Output is correct
10 Correct 70 ms 51780 KB Output is correct
11 Correct 55 ms 48732 KB Output is correct
12 Correct 51 ms 44932 KB Output is correct
13 Correct 51 ms 45032 KB Output is correct
14 Correct 61 ms 46116 KB Output is correct
15 Correct 51 ms 47056 KB Output is correct
16 Correct 54 ms 46128 KB Output is correct
17 Correct 49 ms 44364 KB Output is correct
18 Correct 49 ms 44544 KB Output is correct
19 Correct 33 ms 44000 KB Output is correct
20 Correct 35 ms 44024 KB Output is correct
21 Incorrect 46 ms 44816 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 44672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 89128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44484 KB Output is correct
2 Correct 46 ms 44896 KB Output is correct
3 Correct 52 ms 51424 KB Output is correct
4 Correct 63 ms 54992 KB Output is correct
5 Correct 33 ms 44028 KB Output is correct
6 Correct 34 ms 44060 KB Output is correct
7 Correct 62 ms 56612 KB Output is correct
8 Correct 60 ms 52188 KB Output is correct
9 Correct 59 ms 45000 KB Output is correct
10 Correct 70 ms 51780 KB Output is correct
11 Correct 55 ms 48732 KB Output is correct
12 Correct 51 ms 44932 KB Output is correct
13 Correct 51 ms 45032 KB Output is correct
14 Correct 61 ms 46116 KB Output is correct
15 Correct 51 ms 47056 KB Output is correct
16 Correct 54 ms 46128 KB Output is correct
17 Correct 49 ms 44364 KB Output is correct
18 Correct 49 ms 44544 KB Output is correct
19 Correct 33 ms 44000 KB Output is correct
20 Correct 35 ms 44024 KB Output is correct
21 Execution timed out 1065 ms 44672 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 524292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44484 KB Output is correct
2 Correct 46 ms 44896 KB Output is correct
3 Correct 52 ms 51424 KB Output is correct
4 Correct 63 ms 54992 KB Output is correct
5 Correct 33 ms 44028 KB Output is correct
6 Correct 34 ms 44060 KB Output is correct
7 Correct 62 ms 56612 KB Output is correct
8 Correct 60 ms 52188 KB Output is correct
9 Correct 59 ms 45000 KB Output is correct
10 Correct 70 ms 51780 KB Output is correct
11 Correct 55 ms 48732 KB Output is correct
12 Correct 51 ms 44932 KB Output is correct
13 Correct 51 ms 45032 KB Output is correct
14 Correct 61 ms 46116 KB Output is correct
15 Correct 51 ms 47056 KB Output is correct
16 Correct 54 ms 46128 KB Output is correct
17 Correct 49 ms 44364 KB Output is correct
18 Correct 49 ms 44544 KB Output is correct
19 Correct 33 ms 44000 KB Output is correct
20 Correct 35 ms 44024 KB Output is correct
21 Incorrect 46 ms 44816 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44484 KB Output is correct
2 Correct 46 ms 44896 KB Output is correct
3 Correct 52 ms 51424 KB Output is correct
4 Correct 63 ms 54992 KB Output is correct
5 Correct 33 ms 44028 KB Output is correct
6 Correct 34 ms 44060 KB Output is correct
7 Correct 62 ms 56612 KB Output is correct
8 Correct 60 ms 52188 KB Output is correct
9 Correct 59 ms 45000 KB Output is correct
10 Correct 70 ms 51780 KB Output is correct
11 Correct 55 ms 48732 KB Output is correct
12 Correct 51 ms 44932 KB Output is correct
13 Correct 51 ms 45032 KB Output is correct
14 Correct 61 ms 46116 KB Output is correct
15 Correct 51 ms 47056 KB Output is correct
16 Correct 54 ms 46128 KB Output is correct
17 Correct 49 ms 44364 KB Output is correct
18 Correct 49 ms 44544 KB Output is correct
19 Correct 33 ms 44000 KB Output is correct
20 Correct 35 ms 44024 KB Output is correct
21 Incorrect 46 ms 44816 KB Output isn't correct
22 Halted 0 ms 0 KB -