oj.uz

Submission #910009

# Submission time Handle Problem Language Result Execution time Memory
910009 2024-01-17T18:06:58 Z Tuanlinh123 Food Court (JOI21_foodcourt) C++17
2 / 100
 233 ms 31772 KB 
#include<bits/stdc++.h>
#define ll int
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 6 ms 19036 KB Output is correct
6 Correct 6 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 7 ms 19068 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 7 ms 19000 KB Output is correct
11 Correct 7 ms 19036 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 7 ms 19036 KB Output is correct
14 Correct 7 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 7 ms 18944 KB Output is correct
17 Correct 7 ms 19112 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 6 ms 19036 KB Output is correct
20 Correct 7 ms 19036 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 6 ms 19036 KB Output is correct
6 Correct 6 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 7 ms 19068 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 7 ms 19000 KB Output is correct
11 Correct 7 ms 19036 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 7 ms 19036 KB Output is correct
14 Correct 7 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 7 ms 18944 KB Output is correct
17 Correct 7 ms 19112 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 6 ms 19036 KB Output is correct
20 Correct 7 ms 19036 KB Output is correct
21 Incorrect 7 ms 19036 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 27128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 31772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 6 ms 19036 KB Output is correct
6 Correct 6 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 7 ms 19068 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 7 ms 19000 KB Output is correct
11 Correct 7 ms 19036 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 7 ms 19036 KB Output is correct
14 Correct 7 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 7 ms 18944 KB Output is correct
17 Correct 7 ms 19112 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 6 ms 19036 KB Output is correct
20 Correct 7 ms 19036 KB Output is correct
21 Incorrect 108 ms 27128 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 22992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 6 ms 19036 KB Output is correct
6 Correct 6 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 7 ms 19068 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 7 ms 19000 KB Output is correct
11 Correct 7 ms 19036 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 7 ms 19036 KB Output is correct
14 Correct 7 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 7 ms 18944 KB Output is correct
17 Correct 7 ms 19112 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 6 ms 19036 KB Output is correct
20 Correct 7 ms 19036 KB Output is correct
21 Incorrect 7 ms 19036 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 6 ms 19036 KB Output is correct
6 Correct 6 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 7 ms 19068 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 7 ms 19000 KB Output is correct
11 Correct 7 ms 19036 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 7 ms 19036 KB Output is correct
14 Correct 7 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 7 ms 18944 KB Output is correct
17 Correct 7 ms 19112 KB Output is correct
18 Correct 6 ms 19036 KB Output is correct
19 Correct 6 ms 19036 KB Output is correct
20 Correct 7 ms 19036 KB Output is correct
21 Incorrect 7 ms 19036 KB Output isn't correct
22 Halted 0 ms 0 KB -