oj.uz

Submission #753379

# Submission time Handle Problem Language Result Execution time Memory
753379 2023-06-05T06:23:57 Z bgnbvnbv Food Court (JOI21_foodcourt) C++14
21 / 100
 515 ms 75604 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
    ll sum,pre;
    node()
    {
        sum=0,pre=0;
    }
    node operator+(const node&o)
    {
        node ans;
        ans.sum=sum+o.sum;
        ans.pre=min(pre,sum+o.pre);
        return ans;
    }
}st[4*maxN];
ll q;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=q)
{
    if(l==r)
    {
        st[id].sum+=val;
        st[id].pre=min(st[id].sum,0ll);
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=q)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll seg[4*maxN];
void upd(ll pos,ll val,ll id=1,ll l=1,ll r=q)
{
    if(l==r)
    {
        seg[id]+=val;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) upd(pos,val,id*2,l,mid);
    else upd(pos,val,id*2+1,mid+1,r);
    seg[id]=seg[id*2]+seg[id*2+1];
}

ll quer(ll x)
{
    ll l=1,r=q,id=1;
    while(true)
    {
        ll mid=l+r>>1;
        if(l==r) return l;
        if(seg[id*2+1]<=x)
        {
            x-=seg[id*2+1];
            id=id*2;
            r=mid;
        }
        else
        {
            l=mid+1;
            id=id*2+1;
        }
    }
}
ll n,m,c[maxN];
vector<pli>in[maxN],add[maxN],vec[maxN];
ll ans[maxN];
ll vc[maxN];
void solve()
{
    cin >> n >> m >> q;
    for(int i=1;i<=q;i++)
    {
        ll t;
        cin >> t;
        vc[i]=t;
        if(t==1)
        {
            ll l,r,k;
            cin >> l >> r >> c[i] >> k;
            in[l].pb({i,k});
            in[r+1].pb({i,-k});
            add[l].pb({i,k});
            add[r+1].pb({i,-k});
        }
        else if(t==2)
        {
            ll l,r,k;
            cin >> l >> r >> k;
            in[l].pb({i,-k});
            in[r+1].pb({i,k});
        }
        else
        {
            ll a,b;
            cin >> a >> b;
            vec[a].pb({i,b});
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(auto zz:in[i])
        {
            update(zz.fi,zz.se);
        }
        for(auto zz:add[i])
        {
            upd(zz.fi,zz.se);
        }
        for(auto zz:vec[i])
        {
            auto cc=get(1,zz.fi);
            ll con=cc.sum-cc.pre;
            if(con>=zz.se)
            {
                ans[zz.fi]=c[quer(con-zz.se)];
            }
            else
            {
                ans[zz.fi]=0;
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(vc[i]==3)
        {
            cout << ans[i]<<'\n';
        }
    }

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

foodcourt.cpp: In function 'void update(ll, ll, ll, ll, ll)':
foodcourt.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     ll mid=l+r>>1;
      |            ~^~
foodcourt.cpp: In function 'node get(ll, ll, ll, ll, ll)':
foodcourt.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     ll mid=l+r>>1;
      |            ~^~
foodcourt.cpp: In function 'void upd(ll, ll, ll, ll, ll)':
foodcourt.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     ll mid=l+r>>1;
      |            ~^~
foodcourt.cpp: In function 'll quer(ll)':
foodcourt.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         ll mid=l+r>>1;
      |                ~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 64224 KB Output is correct
2 Correct 324 ms 64516 KB Output is correct
3 Correct 484 ms 72104 KB Output is correct
4 Correct 356 ms 66504 KB Output is correct
5 Correct 353 ms 66680 KB Output is correct
6 Correct 515 ms 74584 KB Output is correct
7 Correct 143 ms 65460 KB Output is correct
8 Correct 148 ms 65964 KB Output is correct
9 Correct 438 ms 73256 KB Output is correct
10 Correct 482 ms 73264 KB Output is correct
11 Correct 431 ms 70092 KB Output is correct
12 Correct 470 ms 73040 KB Output is correct
13 Correct 447 ms 70204 KB Output is correct
14 Correct 448 ms 72864 KB Output is correct
15 Correct 462 ms 72844 KB Output is correct
16 Correct 474 ms 72852 KB Output is correct
17 Correct 473 ms 72816 KB Output is correct
18 Correct 475 ms 71444 KB Output is correct
19 Correct 472 ms 72844 KB Output is correct
20 Correct 512 ms 71540 KB Output is correct
21 Correct 472 ms 72840 KB Output is correct
22 Correct 483 ms 72860 KB Output is correct
23 Correct 493 ms 72896 KB Output is correct
24 Correct 469 ms 72848 KB Output is correct
25 Correct 339 ms 71236 KB Output is correct
26 Correct 362 ms 71876 KB Output is correct
27 Correct 371 ms 75604 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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