Submission #910030

#	Time	Username	Problem	Language	Result	Execution time	Memory
910030		Tuanlinh123	Food Court (JOI21_foodcourt)	C++17	100 / 100	678 ms	52236 KiB

foodcourt

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=250005;
vector <pll> E[maxn], Q[maxn];
ll ans[maxn], g[maxn];
long long cnt[maxn*4], Min[maxn*4], lz[maxn*4];

void Move(ll i)
{
    ll t=lz[i]; lz[i]=0;
    Min[i*2]+=t, Min[i*2+1]+=t;
    lz[i*2]+=t, lz[i*2+1]+=t;
}

void AddCnt(ll i, ll Start, ll End, ll idx, ll val)
{
    if (Start==End)
    {
        cnt[i]+=val;
        return;
    }
    ll mid=(Start+End)/2;
    if (idx<=mid) AddCnt(i*2, Start, mid, idx, val);
    if (idx>=mid+1) AddCnt(i*2+1, mid+1, End, idx, val);
    cnt[i]=cnt[i*2]+cnt[i*2+1];
}

void AddMin(ll i, ll Start, ll End, ll l, ll r, ll val)
{
    if (Start>=l && End<=r)
    {
        Min[i]+=val;
        lz[i]+=val;
        return;
    }
    if (lz[i]) Move(i);
    ll mid=(Start+End)/2;
    if (mid>=l) AddMin(i*2, Start, mid, l, r, val);
    if (mid+1<=r) AddMin(i*2+1, mid+1, End, l, r, val);
    Min[i]=min(Min[i*2], Min[i*2+1]);
}

long long GetCnt(ll i, ll Start, ll End, ll l, ll r)
{
    if (Start>=l && End<=r)
        return cnt[i];
    ll mid=(Start+End)/2;
    if (mid<l) return GetCnt(i*2+1, mid+1, End, l, r);
    if (mid+1>r) return GetCnt(i*2, Start, mid, l, r);
    return GetCnt(i*2, Start, mid, l, r)+GetCnt(i*2+1, mid+1, End, l, r);
}

long long GetMin(ll i, ll Start, ll End, ll l, ll r)
{
    if (Start>=l && End<=r)
        return Min[i];
    if (lz[i]) Move(i);
    ll mid=(Start+End)/2;
    if (mid<l) return GetMin(i*2+1, mid+1, End, l, r);
    if (mid+1>r) return GetMin(i*2, Start, mid, l, r);
    return min(GetMin(i*2, Start, mid, l, r), GetMin(i*2+1, mid+1, End, l, r));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, q; cin >> n >> m >> q;
    for (ll i=1; i<=q; i++)
    {
        ll t; cin >> t;
        if (t==1)
        {
            ll l, r, k; cin >> l >> r >> g[i] >> k;
            E[l].pb({k, i}); E[r+1].pb({-k, i});
            ans[i]=-1;
        }
        else if (t==2)
        {
            ll l, r, k; cin >> l >> r >> k;
            E[l].pb({-k, -i}); E[r+1].pb({k, -i});
            ans[i]=-1;
        }
        else
        {
            ll a, b; cin >> a >> b;
            Q[a].pb({b, i});
        }
    }
    for (ll i=1; i<=n; i++)
    {
        for (pll j:E[i])
        {
            ll k=j.fi, idx=j.se;
            if (idx>0) AddCnt(1, 1, q, idx, k), AddMin(1, 1, q, idx, q, k);
            else AddMin(1, 1, q, -idx, q, k);
        }
        for (pll j:Q[i])
        {
            ll k=j.fi, idx=j.se, Min=GetMin(1, 1, q, 1, idx);
            k-=GetMin(1, 1, q, idx, idx)-GetCnt(1, 1, q, 1, idx)-(Min<=0?Min:0);
            ll lo=1, hi=idx;
            while (hi>lo)
            {
                ll mid=(lo+hi)/2;
                if (GetCnt(1, 1, q, 1, mid)<k)
                    lo=mid+1;
                else hi=mid;
            }
            if (lo!=idx) ans[idx]=g[lo];
        }
    }
    for (ll i=1; i<=q; i++)
        if (ans[i]>=0)
            cout << ans[i] << "\n";
}

• 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