Submission #571891

#	Time	Username	Problem	Language	Result	Execution time	Memory
571891		dantoh000	Food Court (JOI21_foodcourt)	C++14	100 / 100	610 ms	74060 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
int n,m,q;
struct dat{
    int v, pv, id;
};

dat merge(dat a, dat b){
    dat D;
    D.id = (a.pv + b.v > b.pv)?a.id:b.id;
    D.v = a.v + b.v;
    D.pv = max(a.pv + b.v, b.pv);
    return D;
}
struct node{
    int s,e,m;
    dat D;
    int NV;
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e, m = (s+e)/2;
        D.v = D.pv = NV = 0;
        D.id = e;
        if (s != e){
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void up(int x, int nv){
        if (s == e){
            D.v = nv;
            D.pv = nv;
            NV = max(0ll, nv);
            return;
        }
        if (x > m) r->up(x,nv);
        else l->up(x,nv);
        D = merge(l->D, r->D);
        NV = l->NV + r->NV;
    }
    int sum(int qs, int qe){
        if (qs == s && qe == e){
            return NV;
        }
        else if (qs > m) return r->sum(qs, qe);
        else if (qe <= m) return l->sum(qs, qe);
        else{
            return l->sum(qs,m) + r->sum(m+1,qe);
        }
    }
    int find(int X){
        if (s == e) return s;
        if (l->NV >= X) return l->find(X);
        else return r->find(X-l->NV);
    }
    dat findMaxSuffix(int qs, int qe){
        ///printf("%d %d:  %d %d\n",s,e,qs,qe);
        if (qs == s && qe == e){
            return D;
        }
        else if (qs > m) return r->findMaxSuffix(qs, qe);
        else if (qe <= m) return l->findMaxSuffix(qs, qe);
        else{
            dat L = l->findMaxSuffix(qs, m);
            dat R = r->findMaxSuffix(m+1,qe);
            return merge(L, R);
        }
    }
} *root;
int ID[250005];
int ANS[250005];
vector<ii> ups[250005];
vector<ii> qus[250005];
main(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for (int i = 0; i < q; i++){
        int t;
        scanf("%lld",&t);
        if (t == 1){
            int l,r,c,k;
            scanf("%lld%lld%lld%lld",&l,&r,&c,&k);
            ID[i] = c;
            ups[l].push_back({i,k});
            ups[r+1].push_back({i,0});
        }
        else if (t == 2){
            int l,r,k;
            scanf("%lld%lld%lld",&l,&r,&k);
            ups[l].push_back({i,-k});
            ups[r+1].push_back({i,0});
        }
        else{
            int a,b;
            scanf("%lld%lld",&a,&b);
            qus[a].push_back({b,i});
        }
    }
    fill(ANS, ANS+q, -1);
    root = new node(0, q+1);
    for (int i = 1; i <= n; i++){
        //printf("at store %d\n",i);
        for (auto [id, nv] : ups[i]){
            //printf("updating %d to %d\n",id,nv);
            root->up(id, nv);
        }
        for (auto [qv, id]: qus[i]){
            //printf("at store %d, querying for the maxsuffix ending at %d\n",i,id);
            dat res = root->findMaxSuffix(0, id);
            //printf("answer %d %d %d\n",res.v, res.pv, res.id);
            if (res.pv < qv){
                ANS[id] = 0;
                continue;
            }
            int target = res.pv - qv;
            //printf("targeting suffix of %d\n",target);
            int PF = root->sum(0, id);
            //printf("sum  is %d, need to find first prefix that is >= %d\n",PF,PF-target);
            int ret = root->find(PF - target);
            //printf("found at %d\n",ret);
            ANS[id] = ID[ret];

        }
    }
    for (int i = 0; i < q; i++){
        if (ANS[i] != -1) printf("%lld\n",ANS[i]);
    }
}

Compilation message (stderr)

foodcourt.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:104:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |         for (auto [id, nv] : ups[i]){
      |                   ^
foodcourt.cpp:108:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         for (auto [qv, id]: qus[i]){
      |                   ^
foodcourt.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%lld%lld%lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
foodcourt.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%lld%lld%lld%lld",&l,&r,&c,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%lld%lld%lld",&l,&r,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%lld%lld",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• 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