oj.uz

Submission #431376

# Submission time Handle Problem Language Result Execution time Memory
431376 2021-06-17T11:27:46 Z Hideo Food Court (JOI21_foodcourt) C++17
14 / 100
 1000 ms 240840 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define int long long
#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];

set < int > s;
set < int > :: iterator itl;

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;
                s.insert(j);
            }
        }
        else if (t == 2){
            int l, r, k;
            cin >> l >> r >> k;
            int prv = l - 1;
            while (!s.empty()){
                itl = s.lower_bound(prv + 1);
                if (itl == s.end())
                    break;
                int j = *itl;
//                cout << l << ' ' << r << ' ' << j << endl;
                if (j > r)
                    break;
                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;

                }
                if (dq[j].empty())
                    s.erase(j);
                prv = j;
            }
        }
        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:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main (){
      | ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43760 KB Output is correct
2 Correct 86 ms 44292 KB Output is correct
3 Correct 96 ms 53912 KB Output is correct
4 Correct 122 ms 59436 KB Output is correct
5 Correct 35 ms 42956 KB Output is correct
6 Correct 34 ms 42968 KB Output is correct
7 Correct 137 ms 61660 KB Output is correct
8 Correct 125 ms 55248 KB Output is correct
9 Correct 131 ms 44448 KB Output is correct
10 Correct 135 ms 54220 KB Output is correct
11 Correct 138 ms 50284 KB Output is correct
12 Correct 129 ms 44496 KB Output is correct
13 Correct 134 ms 45080 KB Output is correct
14 Correct 177 ms 46368 KB Output is correct
15 Correct 122 ms 47144 KB Output is correct
16 Correct 176 ms 45064 KB Output is correct
17 Correct 85 ms 43556 KB Output is correct
18 Correct 115 ms 43920 KB Output is correct
19 Correct 34 ms 43016 KB Output is correct
20 Correct 41 ms 43104 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43760 KB Output is correct
2 Correct 86 ms 44292 KB Output is correct
3 Correct 96 ms 53912 KB Output is correct
4 Correct 122 ms 59436 KB Output is correct
5 Correct 35 ms 42956 KB Output is correct
6 Correct 34 ms 42968 KB Output is correct
7 Correct 137 ms 61660 KB Output is correct
8 Correct 125 ms 55248 KB Output is correct
9 Correct 131 ms 44448 KB Output is correct
10 Correct 135 ms 54220 KB Output is correct
11 Correct 138 ms 50284 KB Output is correct
12 Correct 129 ms 44496 KB Output is correct
13 Correct 134 ms 45080 KB Output is correct
14 Correct 177 ms 46368 KB Output is correct
15 Correct 122 ms 47144 KB Output is correct
16 Correct 176 ms 45064 KB Output is correct
17 Correct 85 ms 43556 KB Output is correct
18 Correct 115 ms 43920 KB Output is correct
19 Correct 34 ms 43016 KB Output is correct
20 Correct 41 ms 43104 KB Output is correct
21 Correct 105 ms 44160 KB Output is correct
22 Correct 102 ms 44460 KB Output is correct
23 Correct 91 ms 54036 KB Output is correct
24 Correct 125 ms 59724 KB Output is correct
25 Correct 35 ms 42968 KB Output is correct
26 Correct 41 ms 42948 KB Output is correct
27 Correct 147 ms 60988 KB Output is correct
28 Correct 159 ms 56176 KB Output is correct
29 Correct 137 ms 46892 KB Output is correct
30 Correct 157 ms 54040 KB Output is correct
31 Correct 143 ms 50036 KB Output is correct
32 Correct 142 ms 44316 KB Output is correct
33 Correct 150 ms 44764 KB Output is correct
34 Correct 195 ms 47344 KB Output is correct
35 Correct 140 ms 45640 KB Output is correct
36 Correct 205 ms 45036 KB Output is correct
37 Correct 41 ms 43128 KB Output is correct
38 Correct 37 ms 43128 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 43608 KB Output is correct
2 Correct 166 ms 44848 KB Output is correct
3 Correct 168 ms 44740 KB Output is correct
4 Correct 170 ms 44740 KB Output is correct
5 Correct 204 ms 44740 KB Output is correct
6 Correct 215 ms 44844 KB Output is correct
7 Correct 100 ms 43832 KB Output is correct
8 Correct 89 ms 43788 KB Output is correct
9 Correct 142 ms 45416 KB Output is correct
10 Correct 143 ms 44840 KB Output is correct
11 Correct 148 ms 45156 KB Output is correct
12 Correct 141 ms 44732 KB Output is correct
13 Correct 148 ms 44364 KB Output is correct
14 Correct 170 ms 44740 KB Output is correct
15 Correct 238 ms 44852 KB Output is correct
16 Correct 202 ms 45076 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 87044 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 66 ms 43760 KB Output is correct
2 Correct 86 ms 44292 KB Output is correct
3 Correct 96 ms 53912 KB Output is correct
4 Correct 122 ms 59436 KB Output is correct
5 Correct 35 ms 42956 KB Output is correct
6 Correct 34 ms 42968 KB Output is correct
7 Correct 137 ms 61660 KB Output is correct
8 Correct 125 ms 55248 KB Output is correct
9 Correct 131 ms 44448 KB Output is correct
10 Correct 135 ms 54220 KB Output is correct
11 Correct 138 ms 50284 KB Output is correct
12 Correct 129 ms 44496 KB Output is correct
13 Correct 134 ms 45080 KB Output is correct
14 Correct 177 ms 46368 KB Output is correct
15 Correct 122 ms 47144 KB Output is correct
16 Correct 176 ms 45064 KB Output is correct
17 Correct 85 ms 43556 KB Output is correct
18 Correct 115 ms 43920 KB Output is correct
19 Correct 34 ms 43016 KB Output is correct
20 Correct 41 ms 43104 KB Output is correct
21 Correct 139 ms 43608 KB Output is correct
22 Correct 166 ms 44848 KB Output is correct
23 Correct 168 ms 44740 KB Output is correct
24 Correct 170 ms 44740 KB Output is correct
25 Correct 204 ms 44740 KB Output is correct
26 Correct 215 ms 44844 KB Output is correct
27 Correct 100 ms 43832 KB Output is correct
28 Correct 89 ms 43788 KB Output is correct
29 Correct 142 ms 45416 KB Output is correct
30 Correct 143 ms 44840 KB Output is correct
31 Correct 148 ms 45156 KB Output is correct
32 Correct 141 ms 44732 KB Output is correct
33 Correct 148 ms 44364 KB Output is correct
34 Correct 170 ms 44740 KB Output is correct
35 Correct 238 ms 44852 KB Output is correct
36 Correct 202 ms 45076 KB Output is correct
37 Execution timed out 1076 ms 69048 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43760 KB Output is correct
2 Correct 86 ms 44292 KB Output is correct
3 Correct 96 ms 53912 KB Output is correct
4 Correct 122 ms 59436 KB Output is correct
5 Correct 35 ms 42956 KB Output is correct
6 Correct 34 ms 42968 KB Output is correct
7 Correct 137 ms 61660 KB Output is correct
8 Correct 125 ms 55248 KB Output is correct
9 Correct 131 ms 44448 KB Output is correct
10 Correct 135 ms 54220 KB Output is correct
11 Correct 138 ms 50284 KB Output is correct
12 Correct 129 ms 44496 KB Output is correct
13 Correct 134 ms 45080 KB Output is correct
14 Correct 177 ms 46368 KB Output is correct
15 Correct 122 ms 47144 KB Output is correct
16 Correct 176 ms 45064 KB Output is correct
17 Correct 85 ms 43556 KB Output is correct
18 Correct 115 ms 43920 KB Output is correct
19 Correct 34 ms 43016 KB Output is correct
20 Correct 41 ms 43104 KB Output is correct
21 Correct 105 ms 44160 KB Output is correct
22 Correct 102 ms 44460 KB Output is correct
23 Correct 91 ms 54036 KB Output is correct
24 Correct 125 ms 59724 KB Output is correct
25 Correct 35 ms 42968 KB Output is correct
26 Correct 41 ms 42948 KB Output is correct
27 Correct 147 ms 60988 KB Output is correct
28 Correct 159 ms 56176 KB Output is correct
29 Correct 137 ms 46892 KB Output is correct
30 Correct 157 ms 54040 KB Output is correct
31 Correct 143 ms 50036 KB Output is correct
32 Correct 142 ms 44316 KB Output is correct
33 Correct 150 ms 44764 KB Output is correct
34 Correct 195 ms 47344 KB Output is correct
35 Correct 140 ms 45640 KB Output is correct
36 Correct 205 ms 45036 KB Output is correct
37 Correct 41 ms 43128 KB Output is correct
38 Correct 37 ms 43128 KB Output is correct
39 Correct 139 ms 43608 KB Output is correct
40 Correct 166 ms 44848 KB Output is correct
41 Correct 168 ms 44740 KB Output is correct
42 Correct 170 ms 44740 KB Output is correct
43 Correct 204 ms 44740 KB Output is correct
44 Correct 215 ms 44844 KB Output is correct
45 Correct 100 ms 43832 KB Output is correct
46 Correct 89 ms 43788 KB Output is correct
47 Correct 142 ms 45416 KB Output is correct
48 Correct 143 ms 44840 KB Output is correct
49 Correct 148 ms 45156 KB Output is correct
50 Correct 141 ms 44732 KB Output is correct
51 Correct 148 ms 44364 KB Output is correct
52 Correct 170 ms 44740 KB Output is correct
53 Correct 238 ms 44852 KB Output is correct
54 Correct 202 ms 45076 KB Output is correct
55 Execution timed out 1076 ms 69048 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43760 KB Output is correct
2 Correct 86 ms 44292 KB Output is correct
3 Correct 96 ms 53912 KB Output is correct
4 Correct 122 ms 59436 KB Output is correct
5 Correct 35 ms 42956 KB Output is correct
6 Correct 34 ms 42968 KB Output is correct
7 Correct 137 ms 61660 KB Output is correct
8 Correct 125 ms 55248 KB Output is correct
9 Correct 131 ms 44448 KB Output is correct
10 Correct 135 ms 54220 KB Output is correct
11 Correct 138 ms 50284 KB Output is correct
12 Correct 129 ms 44496 KB Output is correct
13 Correct 134 ms 45080 KB Output is correct
14 Correct 177 ms 46368 KB Output is correct
15 Correct 122 ms 47144 KB Output is correct
16 Correct 176 ms 45064 KB Output is correct
17 Correct 85 ms 43556 KB Output is correct
18 Correct 115 ms 43920 KB Output is correct
19 Correct 34 ms 43016 KB Output is correct
20 Correct 41 ms 43104 KB Output is correct
21 Correct 105 ms 44160 KB Output is correct
22 Correct 102 ms 44460 KB Output is correct
23 Correct 91 ms 54036 KB Output is correct
24 Correct 125 ms 59724 KB Output is correct
25 Correct 35 ms 42968 KB Output is correct
26 Correct 41 ms 42948 KB Output is correct
27 Correct 147 ms 60988 KB Output is correct
28 Correct 159 ms 56176 KB Output is correct
29 Correct 137 ms 46892 KB Output is correct
30 Correct 157 ms 54040 KB Output is correct
31 Correct 143 ms 50036 KB Output is correct
32 Correct 142 ms 44316 KB Output is correct
33 Correct 150 ms 44764 KB Output is correct
34 Correct 195 ms 47344 KB Output is correct
35 Correct 140 ms 45640 KB Output is correct
36 Correct 205 ms 45036 KB Output is correct
37 Correct 41 ms 43128 KB Output is correct
38 Correct 37 ms 43128 KB Output is correct
39 Correct 139 ms 43608 KB Output is correct
40 Correct 166 ms 44848 KB Output is correct
41 Correct 168 ms 44740 KB Output is correct
42 Correct 170 ms 44740 KB Output is correct
43 Correct 204 ms 44740 KB Output is correct
44 Correct 215 ms 44844 KB Output is correct
45 Correct 100 ms 43832 KB Output is correct
46 Correct 89 ms 43788 KB Output is correct
47 Correct 142 ms 45416 KB Output is correct
48 Correct 143 ms 44840 KB Output is correct
49 Correct 148 ms 45156 KB Output is correct
50 Correct 141 ms 44732 KB Output is correct
51 Correct 148 ms 44364 KB Output is correct
52 Correct 170 ms 44740 KB Output is correct
53 Correct 238 ms 44852 KB Output is correct
54 Correct 202 ms 45076 KB Output is correct
55 Runtime error 78 ms 87044 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -