Submission #1032009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032009		AdamGS	Food Court (JOI21_foodcourt)	C++17	100 / 100	284 ms	61008 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=25e4+7;
struct pyt {
  ll t=0, l=0, r=0, a=0, b=0;
};
pyt T[LIM];
vector<int>dodaj[LIM], usun[LIM], odp[LIM];
ll tr1[4*LIM], tr2[4*LIM], lazya[4*LIM], lazyb[4*LIM], wynik[LIM], N=1;
void upd1(int l, int r, ll x) {
  if(l>r) return;
  l+=N; r+=N;
  tr1[l]+=x;
  if(l!=r) tr1[r]+=x;
  while(l/2!=r/2) {
    if(l%2==0) tr1[l+1]+=x;
    if(r%2==1) tr1[r-1]+=x;
    l/=2; r/=2;
  }
}
ll cnt1(int v) {
  v+=N;
  ll ans=0;
  while(v) {
    ans+=tr1[v];
    v/=2;
  }
  return ans;
}
void spl(int v) {
  lazya[2*v]+=lazya[v];
  lazyb[2*v]=max(lazyb[2*v]+lazya[v], lazyb[v]);
  lazya[2*v+1]+=lazya[v];
  lazyb[2*v+1]=max(lazyb[2*v+1]+lazya[v], lazyb[v]);
  lazya[v]=0;
  lazyb[v]=-INF;
}
void upd2(int v, int l, int r, int a, int b, ll x, ll y) {
  if(r<a || b<l) return;
  if(a<=l && r<=b) {
    lazya[v]+=x;
    lazyb[v]=max(lazyb[v]+x, y);
    return;
  }
  spl(v);
  int mid=(l+r)/2;
  upd2(2*v, l, mid, a, b, x, y);
  upd2(2*v+1, mid+1, r, a, b, x, y);
}
ll cnt2(int v, int l, int r, int x) {
  if(r<x || x<l) return 0;
  if(l==r) return max(lazya[v], lazyb[v]);
  spl(v);
  int mid=(l+r)/2;
  return cnt2(2*v, l, mid, x)+cnt2(2*v+1, mid+1, r, x);
}
void upd3(int v, ll x) {
  v+=N;
  while(v) {
    tr2[v]+=x;
    v/=2;
  }
}
ll zejdz(ll k) {
  int v=1;
  while(v<N) {
    v*=2;
    if(tr2[v]<k) {
      k-=tr2[v];
      ++v;
    }
  }
  return v-N;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  while(N<max(n, q)) N*=2;
  rep(i, q) {
    cin >> T[i].t;
    if(T[i].t==1) {
      cin >> T[i].l >> T[i].r >> T[i].a >> T[i].b;
      --T[i].l; --T[i].r;
      dodaj[T[i].l].pb(i);
      usun[T[i].r].pb(i);
      upd1(T[i].l, T[i].r, T[i].b);
      upd2(1, 0, N-1, T[i].l, T[i].r, T[i].b, 0);
    } else if(T[i].t==2) {
      cin >> T[i].l >> T[i].r >> T[i].a;
      --T[i].l; --T[i].r;
      upd2(1, 0, N-1, T[i].l, T[i].r, -T[i].a, 0);
    } else {
      cin >> T[i].a >> T[i].b;
      --T[i].a;
      ll x=cnt1(T[i].a), y=cnt2(1, 0, N-1, T[i].a);
      if(y<T[i].b) continue;
      T[i].l=x-y+T[i].b;
      odp[T[i].a].pb(i);
    }
  }
  rep(i, n) {
    for(auto j : dodaj[i]) upd3(j, T[j].b);
    for(auto j : odp[i]) {
      ll x=zejdz(T[j].l);
      wynik[j]=T[x].a;
    }
    for(auto j : usun[i]) upd3(j, -T[j].b);
  }
  rep(i, q) if(T[i].t==3) cout << wynik[i] << '\n';
}

• 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