제출 #797275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797275		vjudge1	Food Court (JOI21_foodcourt)	C++98	0 / 100	196 ms	182484 KiB

foodcourt

#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)
{
    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 && m <= 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 ;
    }
    if(n <= 65000 && q <= 65000)
    {
        bool flag1 = 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(r[i] - l[i] > 10 || k[i] != 1)
                    flag1 = 1 ;
            }
            if(type[i] == 2)
                cin >> l[i] >> r[i] >> k[i] ;
            if(type[i] == 3)
                cin >> a[i] >> b[i] ;
        }
        if(!flag1)
        {
            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, 0, 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], 0, 1) ;
                    if(b[i] <= d[a[i]].size())
                        cout << d[a[i]][b[i] - 1].fi << '\n' ;
                    else
                        cout << "0\n" ;
                }
            }
            return 0 ;
        }
    }
    if(m == 1)
    {
        while(m--)
        {
        }
        return 0 ;
    }
    return 0 ;
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:143:32: 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]
  143 |                         if(num >= d[j].size())
      |                            ~~~~^~~~~~~~~~~~~~
foodcourt.cpp:159:28: 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]
  159 |                     if(num >= d[a[i]].size())
      |                        ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:167:29: 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]
  167 |                     if(b[i] <= d[a[i]].size())
      |                        ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11