Submission #553593

#	Time	Username	Problem	Language	Result	Execution time	Memory
553593		Killer2501	Food Court (JOI21_foodcourt)	C++14	100 / 100	474 ms	75468 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<ll, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, t, d[N], cnt, par[N];
ll ans, tong;
vector<int> adj[N];
vector<pii> add[N], itadd[N], query[N];
bool vis[N], ok;

struct node
{
    ll sum, suf;
    node()
    {
        sum = 0;
        suf = 0;
    }
    node(ll _sum, ll _suf)
    {
        sum = _sum;
        suf = _suf;
    }
};
node merga(node x, node y)
{
    node res;
    res.sum = x.sum+y.sum;
    res.suf = max(x.suf+y.sum, y.suf);
    return res;
}
struct IT
{
    int n;
    vector<node> st;
    IT(int _n)
    {
        n = _n;
        st.resize(n*4+4);
    }
    void build(int id, int l, int r, int pos, ll x)
    {
        if(l == r)
        {
            st[id] = node(x, x);
            return;
        }
        int mid = (l+r)>>1;
        if(pos <= mid)build(id<<1, l, mid, pos, x);
        else build(id<<1|1, mid+1, r, pos, x);
        st[id] = merga(st[id<<1], st[id<<1|1]);
    }
    void build(int pos, ll x)
    {
        build(1, 1, n, pos, x);
    }
    node get(int id, int l, int r, int u, int v)
    {
        if(u <= l && r <= v)return st[id];
        if(u > r || l > v)return node(0, 0);
        int mid = (l+r)>>1;
        return merga(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
    }
    node get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
};
struct BIT
{
    int n;
    vector<ll> fe;
    BIT(int _n)
    {
        n = _n;
        fe.resize(n+1, 0);
    }
    void add(int id, ll x)
    {
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    ll get(int id)
    {
        ll total = 0;
        for(; id; id -= id & -id)total += fe[id];
        return total;
    }
    int getK(ll v)
    {
        int pos = 0;
        for(int j = 18; j >= 0; j --)
        {
            pos += (1<<j);
            if(pos <= n && fe[pos] < v)v -= fe[pos];
            else pos -= (1<<j);
        }
        return pos+1;
    }
};
void sol()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++)
    {
        a[i] = -1;
        cin >> t;
        if(t == 1)
        {
            int li, ri, ci;
            ll ki;
            cin >> li >> ri >> ci >> ki;
            add[li].pb({ki, i});
            add[ri+1].pb({-ki, i});
            itadd[li].pb({ki, i});
            itadd[ri+1].pb({0, i});
            d[i] = ci;
        }
        else if(t == 2)
        {
            int li, ri;
            ll ki;
            cin >> li >> ri >> ki;
            itadd[li].pb({-ki, i});
            itadd[ri+1].pb({0, i});
        }
        else
        {
            int li;
            ll ki;
            cin >> li >> ki;
            query[li].pb({ki, i});
        }
    }
    IT it(k);
    BIT bit(k);
    for(int i = 1; i <= n; i ++)
    {
        for(pii x: add[i])bit.add(x.se, x.fi);
        for(pii x: itadd[i])
        {
            //cout << x.se <<" "<<x.fi<<" "<<i<<'\n';
            it.build(x.se, x.fi);
        }
        for(pii x: query[i])
        {
            ans = it.get(1, x.se).suf;
            if(ans < x.fi)a[x.se] = 0;
            else a[x.se] = d[bit.getK(bit.get(x.se)-(ans-x.fi))];
        }
    }
    for(int i = 1; i <= k; i ++)if(a[i] != -1)cout << a[i]<<'\n';
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
2 1 6 5 4 3
*/

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:172:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:173:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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