Submission #525954

#	Time	Username	Problem	Language	Result	Execution time	Memory
525954		ivan_tudor	Food Court (JOI21_foodcourt)	C++14	100 / 100	560 ms	54020 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
const int N = 250005;
struct ainthelp{
  long long lazy;
  long long minv;
  int minp;
};
ainthelp aint[4*N];
void propag(int nod, int l, int r){
  aint[nod].minv += aint[nod].lazy;
  if(l != r){
    aint[2*nod].lazy += aint[nod].lazy;
    aint[2*nod + 1].lazy += aint[nod].lazy;
  }
  aint[nod].lazy = 0;
}
ainthelp join(ainthelp a, ainthelp b){
  ainthelp rsp;
  rsp.lazy = 0;
  if(a.minv < b.minv){
    rsp.minv = a.minv;
    rsp.minp = a.minp;
  }
  else if(b.minv < a.minv){
    rsp.minv = b.minv;
    rsp.minp = b.minp;
  }
  else if(a.minv == b.minv){
    rsp.minv = a.minv;
    rsp.minp = max(a.minp, b.minp);
  }
  return rsp;
}
void aint_build(int nod, int l, int r){
  if(l == r){
    aint[nod].lazy = aint[nod].minv = 0;
    aint[nod].minp = l;
    return;
  }
  int mid = (l +r)/2;
  aint_build(2*nod, l, mid);
  aint_build(2*nod + 1, mid + 1, r);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
void update(int nod, int l, int r, int ul, int ur, long long val){
  propag(nod, l, r);
  if(r < ul || ur < l)
    return;
  if(ul <= l && r <= ur){
    aint[nod].lazy += val;
    propag(nod, l, r);
    return;
  }
  int mid = (l +r)/2;
  update(2*nod, l, mid, ul, ur, val);
  update(2*nod + 1, mid + 1, r, ul, ur, val);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
long long querypoz(int nod, int l, int r, int poz){
  propag(nod, l, r);
  if(poz < l || poz > r)
    return LLONG_MIN;
  if(l == r)
    return aint[nod].minv;
  int mid = (l + r)/2;
  long long ls = querypoz(2*nod, l, mid, poz);
  long long dr = querypoz(2*nod + 1, mid + 1, r, poz);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
  return max(ls, dr);
}
ainthelp queryitv(int nod, int l, int r, int ql, int qr){
  propag(nod, l, r);
  if(r < ql || l > qr)
    return {0, LLONG_MAX, INT_MAX};
  if(ql <= l && r <= qr)
    return aint[nod];
  int mid = (l +r)/2;
  ainthelp left = queryitv(2*nod, l, mid, ql, qr);
  ainthelp right = queryitv(2*nod + 1, mid + 1, r, ql, qr);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
  return join(left, right);
}
long long aibpoz[N];
void aib_upd(int poz, long long val){
  for(int i = poz; i < N; i += i&(-i))
    aibpoz[i] += val;
}
long long aib_query(int poz){
  long long rsp = 0;
  for(int i = poz; i >0; i-= i&(-i)){
    rsp += aibpoz[i];
  }
  return rsp;
}
int aib_bs(long long val){ /// first >= val
  int pas = 0;
  for(int p2 = 1<<20; p2>0; p2>>=1){
    if(pas + p2 < N && aibpoz[pas + p2] < val){
      pas += p2;
      val -= aibpoz[pas];
    }
  }
  return pas + 1;
}
struct updates{
  long long val; /// val > 0, group > 0 => type 1; val < 0 => type = 2
  int group;
};
updates tme[N];
struct smenhelper{
  int type; /// add(1), erase(-1)
  int time;
  updates upd;

};

vector<smenhelper> smen[N];
vector<smenhelper> queries[N];
int answers[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m, q;
  cin>>n>>m>>q;
  for(int i = 1; i <=q; i++){
    answers[i] = -1;
    int t;
    cin>>t;
    if(t == 1){
      int l, r, gr;
      long long val;
      cin>>l>>r>>gr>>val;
      smenhelper addval{1, i, {val, gr}};
      smen[l].push_back(addval);

      smenhelper delval{-1, i, {val, gr}};
      smen[r + 1].push_back(delval);
    }
    else if(t == 2){
      int l, r, gr;
      long long val;
      cin>>l>>r>>val;
      smenhelper addval{1, i, {-val, 0}};
      smen[l].push_back(addval);

      smenhelper delval{-1, i, {-val, 0}};
      smen[r + 1].push_back(delval);
    }
    else if(t == 3){
      int poz;
      long long val;
      cin>>poz>>val;
      smenhelper qry{0, i, {val, 0}};
      queries[poz].push_back(qry);
    }
  }
  ///aint size = q ( TMAX = q)
  /// aint de la 0 la q
  aint_build(1, 0, q);
  for(int i = 1; i<=n; i++){
    for(auto change:smen[i]){
      if(change.type == 1){ ///insert new update
        updates upd = change.upd;
        tme[change.time] = upd;
        if(upd.val > 0){ /// type = 1 => new members in queues
          update(1, 0, q, change.time, q, 1LL*upd.val);
          aib_upd(change.time, 1LL * upd.val);
        }
        else if(upd.val < 0){ /// type = 2 => leave from queue
          update(1, 0, q, change.time, q, 1LL * upd.val);
        }
      }
      else if(change.type == -1){ /// delete old update
        updates upd = change.upd;
        tme[change.time] = {0, 0};
        if(upd.val > 0){ ///type = 1 => have to remove old members
          update(1, 0, q, change.time, q, -1LL * upd.val);
          aib_upd(change.time, -1LL * upd.val);
        }
        else if(upd.val <0){ ///type = 2 => have to add them back
            update(1, 0, q, change.time, q, -1LL * upd.val);
        }
      }
    }
    for(auto qry:queries[i]){
      int time = qry.time;
      long long val = qry.upd.val;

      ainthelp minq = queryitv(1, 0, q, 0, time);
      long long minval = minq.minv;
      long long lastval = querypoz(1, 0, q, time);
      long long cval = lastval - minval;
      if(val > cval){
        answers[time] = 0;
      }
      else{
        long long alladded = aib_query(time);
        long long lookingfor = alladded - (cval - val);
        int id = aib_bs(lookingfor);
        answers[time] = tme[id].group;
      }
    }
  }
  for(int i = 1; i <=q; i++){
    if(answers[i] != -1)
      cout<<answers[i]<<"\n";
  }
  return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:143:17: warning: unused variable 'gr' [-Wunused-variable]
  143 |       int l, r, gr;
      |                 ^~

• 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