Submission #1246513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246513		hainam2k9	Food Court (JOI21_foodcourt)	C++20	100 / 100	374 ms	41072 KiB

foodcourt

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2.5e5+5;
const string NAME = "";
struct SegmentTree{
    pair<ll,ll> sgt[MAXN<<2];
    void update(int id, int l, int r, int pos, int val){
        if(pos<l||r<pos) return;
        if(l==r){
            sgt[id].fi+=val;
            sgt[id].se=min(0ll,sgt[id].fi);
            return;
        }
        int mid=(l+r)>>1;
        update(id<<1,l,mid,pos,val);
        update(id<<1|1,mid+1,r,pos,val);
        sgt[id].fi=sgt[id<<1].fi+sgt[id<<1|1].fi;
        sgt[id].se=min(sgt[id<<1].se,sgt[id<<1].fi+sgt[id<<1|1].se);
    }
    pair<ll,ll> get(int id, int l, int r, int pos){
        if(l>pos) return {0,0};
        if(r<=pos) return sgt[id];
        int mid=(l+r)>>1;
        pair<ll,ll> Left=get(id<<1,l,mid,pos), Right=get(id<<1|1,mid+1,r,pos);
        return {Left.fi+Right.fi,min(Left.se,Left.fi+Right.se)};
    }
}sgt;
struct BIT{
    ll n,bit[MAXN];
    void update(int pos, int val){
        while(pos<=n) bit[pos]+=val, pos+=pos&-pos;
    }
    ll getsum(int pos){
        ll rs=0;
        while(pos>0) rs+=bit[pos], pos-=pos&-pos;
        return rs;
    }
    int bs(ll bound){
        int rs=0;
        ll sum=0;
        for(int i = __lg(n); i>=0; --i){
            int nxt=rs|(1<<i);
            if(nxt<=n&&sum+bit[nxt]<bound) rs=nxt, sum+=bit[nxt];
        }
        return rs+1;
    }
}bit;
int n,m,q,rs[MAXN],group[MAXN];
vector<pair<int,int>> add[MAXN],del[MAXN];
vector<pair<int,ll>> query[MAXN];
vector<int> vdel;
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    memset(rs,-1,sizeof(rs));
    cin >> n >> m >> q;
    for(int i = 1; i<=q; ++i){
        int type,l,r;
        ll a,b;
        cin >> type;
        if(type==1){
            cin >> l >> r >> group[i] >> b;
            add[l].pb(i,b), add[r+1].pb(i,-b);
        }else if(type==2){
            cin >> l >> r >> a;
            del[l].pb(i,-a), del[r+1].pb(i,a);
            vdel.pb(i);
        }else{
            cin >> a >> b;
            query[a].pb(i,b);
        }
    }
    bit.n=q;
    for(int i = 1; i<=n; ++i){
        for(pair<int,int>& p : add[i]){
            bit.update(p.fi,p.se);
            sgt.update(1,1,q,p.fi,p.se);
        }
        for(pair<int,int>& p : del[i]){
            sgt.update(1,1,q,p.fi,p.se);
        }
        for(pair<int,ll>& p : query[i]){
            pair<ll,ll> cur=sgt.get(1,1,q,p.fi);
            if(cur.fi-cur.se>=p.se) rs[p.fi]=group[bit.bs(bit.getsum(p.fi)-cur.fi+cur.se+p.se)];
            else rs[p.fi]=0;
        }
    }
    for(int i = 1; i<=q; ++i)
        if(rs[i]!=-1) cout << rs[i] << "\n";
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:72:45: note: in expansion of macro 'fo'
   72 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
foodcourt.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:72:45: note: in expansion of macro 'fo'
   72 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

• 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