oj.uz

Submission #797285

# Submission time Handle Problem Language Result Execution time Memory
797285 2023-07-29T08:48:51 Z vjudge1 Food Court (JOI21_foodcourt) C++
14 / 100
 1000 ms 219828 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 18) ;
ll n, m, q, sum[2 * N + 1], psh[2 * N + 1] ;
deque<pair<ll, ll>> d[N + 1] ;
void push(ll l, ll r, ll v)
{
    if(!psh[v])
        return ;
    ll num = psh[v] ;
    psh[v] = 0 ;
    sum[v] += num * (r - l + 1) ;
    if(l == r)
        return ;
    psh[2 * v] += num ;
    psh[2 * v + 1] += num ;
}
void update(ll l, ll r, ll l1, ll r1, ll num, ll v)
{
    push(l, r, v) ;
    if(l > r1 || r < l1)
        return ;
    if(l1 <= l && r <= r1)
    {
        psh[v] = num ;
        push(l, r, v) ;
        return ;
    }
    ll mid = (l + r) >> 1 ;
    update(l, mid, l1, r1, num, v * 2) ;
    update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
    sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
ll get_sum(ll l, ll r, ll pos, ll v)
{
    push(l, r, v) ;
    if(l > pos || r < pos)
        return 0 ;
    if(l == r)
        return sum[v] ;
    ll mid = (l + r) >> 1 ;
    return get_sum(l, mid, pos, v * 2) + get_sum(mid + 1, r, pos, v * 2 + 1) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m >> q ;
    if(n <= 2000 && q <= 2000)
    {
        while(q--)
        {
            ll type, l, r, c, k, a, b ;
            cin >> type ;
            if(type == 1)
            {
                cin >> l >> r >> c >> k ;
                for(ll i = l ; i <= r ; i++)
                    d[i].push_back({c, k}) ;
            }
            if(type == 2)
            {
                cin >> l >> r >> k ;
                for(ll i = l ; i <= r ; i++)
                {
                    ll sum = 0, k1 = k ;
                    for(auto j : d[i])
                        sum += j.se ;
                    if(sum < k1)
                    {
                        d[i].clear() ;
                        continue ;
                    }
                    while(k1)
                        if(d[i][0].se <= k1)
                        {
                            k1 -= d[i][0].se ;
                            d[i].pop_front() ;
                        }
                        else
                        {
                            pair<ll, ll> p = {d[i][0].fi, d[i][0].se - k1} ;
                            d[i].pop_front() ;
                            d[i].push_front(p) ;
                            k1 = 0 ;
                        }
                }
            }
            if(type == 3)
            {
                ll sum = 0, ans = 0 ;
                cin >> a >> b ;
                for(auto i : d[a])
                    sum += i.se ;
                if(sum < b)
                {
                    cout << "0\n" ;
                    continue ;
                }
                for(auto i : d[a])
                    if(i.se < b)
                        b -= i.se ;
                    else
                    {
                        ans = i.fi ;
                        break ;
                    }
                cout << ans << "\n" ;
            }
        }
        return 0 ;
    }
    ll type[q + 1], l[q + 1], r[q + 1], c[q + 1], k[q + 1], a[q + 1], b[q + 1] ;
    for(ll i = 1 ; i <= q ; i++)
    {
        cin >> type[i] ;
        if(type[i] == 1)
        {
            cin >> l[i] >> r[i] >> c[i] >> k[i] ;
        }
        if(type[i] == 2)
            cin >> l[i] >> r[i] >> k[i] ;
        if(type[i] == 3)
            cin >> a[i] >> b[i] ;
    }
    for(ll i = 1 ; i <= q ; i++)
    {
        if(type[i] == 1)
        {
            for(ll j = l[i] ; j <= r[i] ; j++)
            {
                ll num = get_sum(1, N, j, 1) ;
                if(num >= d[j].size())
                    d[j].clear() ;
                else
                {
                    for(ll q = 1 ; q <= num ; q++)
                        d[j].pop_front() ;
                }
                update(1, N, j, j, -num, 1) ;
                d[j].push_back({c[i], k[i]}) ;
            }
        }
        if(type[i] == 2)
            update(1, N, l[i], r[i], k[i], 1) ;
        if(type[i] == 3)
        {
            ll num = get_sum(1, N, a[i], 1) ;
            if(num >= d[a[i]].size())
                d[a[i]].clear() ;
            else
            {
                for(ll j = 1 ; j <= num ; j++)
                    d[a[i]].pop_front() ;
            }
            update(1, N, a[i], a[i], -num, 1) ;
            if(b[i] <= d[a[i]].size())
                cout << d[a[i]][b[i] - 1].fi << '\n' ;
            else
                cout << "0\n" ;
        }
    }
    return 0 ;
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:137:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                 if(num >= d[j].size())
      |                    ~~~~^~~~~~~~~~~~~~
foodcourt.cpp:153:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             if(num >= d[a[i]].size())
      |                ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:161:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             if(b[i] <= d[a[i]].size())
      |                ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 177236 KB Output is correct
2 Correct 111 ms 177596 KB Output is correct
3 Correct 128 ms 184220 KB Output is correct
4 Correct 180 ms 187764 KB Output is correct
5 Correct 93 ms 176784 KB Output is correct
6 Correct 96 ms 176780 KB Output is correct
7 Correct 232 ms 189268 KB Output is correct
8 Correct 187 ms 184924 KB Output is correct
9 Correct 117 ms 177484 KB Output is correct
10 Correct 187 ms 184320 KB Output is correct
11 Correct 165 ms 181472 KB Output is correct
12 Correct 114 ms 177648 KB Output is correct
13 Correct 122 ms 177720 KB Output is correct
14 Correct 130 ms 178816 KB Output is correct
15 Correct 148 ms 179660 KB Output is correct
16 Correct 125 ms 178784 KB Output is correct
17 Correct 101 ms 177136 KB Output is correct
18 Correct 109 ms 177224 KB Output is correct
19 Correct 85 ms 176748 KB Output is correct
20 Correct 93 ms 176784 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 177236 KB Output is correct
2 Correct 111 ms 177596 KB Output is correct
3 Correct 128 ms 184220 KB Output is correct
4 Correct 180 ms 187764 KB Output is correct
5 Correct 93 ms 176784 KB Output is correct
6 Correct 96 ms 176780 KB Output is correct
7 Correct 232 ms 189268 KB Output is correct
8 Correct 187 ms 184924 KB Output is correct
9 Correct 117 ms 177484 KB Output is correct
10 Correct 187 ms 184320 KB Output is correct
11 Correct 165 ms 181472 KB Output is correct
12 Correct 114 ms 177648 KB Output is correct
13 Correct 122 ms 177720 KB Output is correct
14 Correct 130 ms 178816 KB Output is correct
15 Correct 148 ms 179660 KB Output is correct
16 Correct 125 ms 178784 KB Output is correct
17 Correct 101 ms 177136 KB Output is correct
18 Correct 109 ms 177224 KB Output is correct
19 Correct 85 ms 176748 KB Output is correct
20 Correct 93 ms 176784 KB Output is correct
21 Correct 106 ms 177352 KB Output is correct
22 Correct 112 ms 177684 KB Output is correct
23 Correct 143 ms 184140 KB Output is correct
24 Correct 159 ms 187864 KB Output is correct
25 Correct 92 ms 176708 KB Output is correct
26 Correct 105 ms 176788 KB Output is correct
27 Correct 240 ms 188732 KB Output is correct
28 Correct 209 ms 185680 KB Output is correct
29 Correct 138 ms 179420 KB Output is correct
30 Correct 191 ms 183884 KB Output is correct
31 Correct 166 ms 181376 KB Output is correct
32 Correct 120 ms 177540 KB Output is correct
33 Correct 110 ms 177632 KB Output is correct
34 Correct 150 ms 179868 KB Output is correct
35 Correct 126 ms 178360 KB Output is correct
36 Correct 130 ms 178824 KB Output is correct
37 Correct 86 ms 176792 KB Output is correct
38 Correct 87 ms 176776 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 182504 KB Output is correct
2 Correct 193 ms 182480 KB Output is correct
3 Correct 218 ms 182560 KB Output is correct
4 Correct 206 ms 182468 KB Output is correct
5 Correct 285 ms 182472 KB Output is correct
6 Correct 258 ms 182580 KB Output is correct
7 Correct 110 ms 180132 KB Output is correct
8 Correct 116 ms 180280 KB Output is correct
9 Correct 182 ms 182500 KB Output is correct
10 Correct 182 ms 182560 KB Output is correct
11 Correct 181 ms 182480 KB Output is correct
12 Correct 178 ms 182476 KB Output is correct
13 Correct 196 ms 181496 KB Output is correct
14 Correct 244 ms 182492 KB Output is correct
15 Correct 234 ms 181784 KB Output is correct
16 Correct 245 ms 182476 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 177236 KB Output is correct
2 Correct 111 ms 177596 KB Output is correct
3 Correct 128 ms 184220 KB Output is correct
4 Correct 180 ms 187764 KB Output is correct
5 Correct 93 ms 176784 KB Output is correct
6 Correct 96 ms 176780 KB Output is correct
7 Correct 232 ms 189268 KB Output is correct
8 Correct 187 ms 184924 KB Output is correct
9 Correct 117 ms 177484 KB Output is correct
10 Correct 187 ms 184320 KB Output is correct
11 Correct 165 ms 181472 KB Output is correct
12 Correct 114 ms 177648 KB Output is correct
13 Correct 122 ms 177720 KB Output is correct
14 Correct 130 ms 178816 KB Output is correct
15 Correct 148 ms 179660 KB Output is correct
16 Correct 125 ms 178784 KB Output is correct
17 Correct 101 ms 177136 KB Output is correct
18 Correct 109 ms 177224 KB Output is correct
19 Correct 85 ms 176748 KB Output is correct
20 Correct 93 ms 176784 KB Output is correct
21 Correct 172 ms 182504 KB Output is correct
22 Correct 193 ms 182480 KB Output is correct
23 Correct 218 ms 182560 KB Output is correct
24 Correct 206 ms 182468 KB Output is correct
25 Correct 285 ms 182472 KB Output is correct
26 Correct 258 ms 182580 KB Output is correct
27 Correct 110 ms 180132 KB Output is correct
28 Correct 116 ms 180280 KB Output is correct
29 Correct 182 ms 182500 KB Output is correct
30 Correct 182 ms 182560 KB Output is correct
31 Correct 181 ms 182480 KB Output is correct
32 Correct 178 ms 182476 KB Output is correct
33 Correct 196 ms 181496 KB Output is correct
34 Correct 244 ms 182492 KB Output is correct
35 Correct 234 ms 181784 KB Output is correct
36 Correct 245 ms 182476 KB Output is correct
37 Execution timed out 1073 ms 193452 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 1087 ms 219828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 177236 KB Output is correct
2 Correct 111 ms 177596 KB Output is correct
3 Correct 128 ms 184220 KB Output is correct
4 Correct 180 ms 187764 KB Output is correct
5 Correct 93 ms 176784 KB Output is correct
6 Correct 96 ms 176780 KB Output is correct
7 Correct 232 ms 189268 KB Output is correct
8 Correct 187 ms 184924 KB Output is correct
9 Correct 117 ms 177484 KB Output is correct
10 Correct 187 ms 184320 KB Output is correct
11 Correct 165 ms 181472 KB Output is correct
12 Correct 114 ms 177648 KB Output is correct
13 Correct 122 ms 177720 KB Output is correct
14 Correct 130 ms 178816 KB Output is correct
15 Correct 148 ms 179660 KB Output is correct
16 Correct 125 ms 178784 KB Output is correct
17 Correct 101 ms 177136 KB Output is correct
18 Correct 109 ms 177224 KB Output is correct
19 Correct 85 ms 176748 KB Output is correct
20 Correct 93 ms 176784 KB Output is correct
21 Correct 106 ms 177352 KB Output is correct
22 Correct 112 ms 177684 KB Output is correct
23 Correct 143 ms 184140 KB Output is correct
24 Correct 159 ms 187864 KB Output is correct
25 Correct 92 ms 176708 KB Output is correct
26 Correct 105 ms 176788 KB Output is correct
27 Correct 240 ms 188732 KB Output is correct
28 Correct 209 ms 185680 KB Output is correct
29 Correct 138 ms 179420 KB Output is correct
30 Correct 191 ms 183884 KB Output is correct
31 Correct 166 ms 181376 KB Output is correct
32 Correct 120 ms 177540 KB Output is correct
33 Correct 110 ms 177632 KB Output is correct
34 Correct 150 ms 179868 KB Output is correct
35 Correct 126 ms 178360 KB Output is correct
36 Correct 130 ms 178824 KB Output is correct
37 Correct 86 ms 176792 KB Output is correct
38 Correct 87 ms 176776 KB Output is correct
39 Correct 172 ms 182504 KB Output is correct
40 Correct 193 ms 182480 KB Output is correct
41 Correct 218 ms 182560 KB Output is correct
42 Correct 206 ms 182468 KB Output is correct
43 Correct 285 ms 182472 KB Output is correct
44 Correct 258 ms 182580 KB Output is correct
45 Correct 110 ms 180132 KB Output is correct
46 Correct 116 ms 180280 KB Output is correct
47 Correct 182 ms 182500 KB Output is correct
48 Correct 182 ms 182560 KB Output is correct
49 Correct 181 ms 182480 KB Output is correct
50 Correct 178 ms 182476 KB Output is correct
51 Correct 196 ms 181496 KB Output is correct
52 Correct 244 ms 182492 KB Output is correct
53 Correct 234 ms 181784 KB Output is correct
54 Correct 245 ms 182476 KB Output is correct
55 Execution timed out 1073 ms 193452 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 177236 KB Output is correct
2 Correct 111 ms 177596 KB Output is correct
3 Correct 128 ms 184220 KB Output is correct
4 Correct 180 ms 187764 KB Output is correct
5 Correct 93 ms 176784 KB Output is correct
6 Correct 96 ms 176780 KB Output is correct
7 Correct 232 ms 189268 KB Output is correct
8 Correct 187 ms 184924 KB Output is correct
9 Correct 117 ms 177484 KB Output is correct
10 Correct 187 ms 184320 KB Output is correct
11 Correct 165 ms 181472 KB Output is correct
12 Correct 114 ms 177648 KB Output is correct
13 Correct 122 ms 177720 KB Output is correct
14 Correct 130 ms 178816 KB Output is correct
15 Correct 148 ms 179660 KB Output is correct
16 Correct 125 ms 178784 KB Output is correct
17 Correct 101 ms 177136 KB Output is correct
18 Correct 109 ms 177224 KB Output is correct
19 Correct 85 ms 176748 KB Output is correct
20 Correct 93 ms 176784 KB Output is correct
21 Correct 106 ms 177352 KB Output is correct
22 Correct 112 ms 177684 KB Output is correct
23 Correct 143 ms 184140 KB Output is correct
24 Correct 159 ms 187864 KB Output is correct
25 Correct 92 ms 176708 KB Output is correct
26 Correct 105 ms 176788 KB Output is correct
27 Correct 240 ms 188732 KB Output is correct
28 Correct 209 ms 185680 KB Output is correct
29 Correct 138 ms 179420 KB Output is correct
30 Correct 191 ms 183884 KB Output is correct
31 Correct 166 ms 181376 KB Output is correct
32 Correct 120 ms 177540 KB Output is correct
33 Correct 110 ms 177632 KB Output is correct
34 Correct 150 ms 179868 KB Output is correct
35 Correct 126 ms 178360 KB Output is correct
36 Correct 130 ms 178824 KB Output is correct
37 Correct 86 ms 176792 KB Output is correct
38 Correct 87 ms 176776 KB Output is correct
39 Correct 172 ms 182504 KB Output is correct
40 Correct 193 ms 182480 KB Output is correct
41 Correct 218 ms 182560 KB Output is correct
42 Correct 206 ms 182468 KB Output is correct
43 Correct 285 ms 182472 KB Output is correct
44 Correct 258 ms 182580 KB Output is correct
45 Correct 110 ms 180132 KB Output is correct
46 Correct 116 ms 180280 KB Output is correct
47 Correct 182 ms 182500 KB Output is correct
48 Correct 182 ms 182560 KB Output is correct
49 Correct 181 ms 182480 KB Output is correct
50 Correct 178 ms 182476 KB Output is correct
51 Correct 196 ms 181496 KB Output is correct
52 Correct 244 ms 182492 KB Output is correct
53 Correct 234 ms 181784 KB Output is correct
54 Correct 245 ms 182476 KB Output is correct
55 Execution timed out 1046 ms 196076 KB Time limit exceeded
56 Halted 0 ms 0 KB -