Submission #1189155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189155		mychecksedad	Food Court (JOI21_foodcourt)	C++20	100 / 100	280 ms	97304 KiB

foodcourt

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;

int n, m, q;
vector<array<ll, 3>> Q[N], QQ[N];
array<ll, 3> T[N]; // remove, add, id
ll TT[N];

void comb(int k){
  if(T[k<<1|1][0] >= T[k<<1][1]){
    T[k] = {T[k<<1][0] + T[k<<1|1][0] - T[k<<1][1], T[k<<1|1][1], -1};
  }else{
    T[k] = {T[k<<1][0], T[k<<1][1] - T[k<<1|1][0] + T[k<<1|1][1], -1};
  }
  TT[k] = TT[k<<1] + TT[k<<1|1];
}

void add(int l, int r, int p, int k, int c, ll val){
  if(l == r){
    if(val < 0){
      T[k] = {-val, 0, c};
      TT[k] = 0;
    }else{
      T[k] = {0, val, c};
      TT[k] = val;
    }
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) add(l, mid, p, k<<1, c, val);
  else add(mid+1, r, p, k<<1|1, c, val);
  comb(k);
}

void rem(int l, int r, int p, int k, int c, ll val){
  if(l == r){
    T[k] = {0, 0, -1};
    TT[k] = 0;
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) rem(l, mid, p, k<<1, c, val);
  else rem(mid+1, r, p, k<<1|1, c, val);
  comb(k);
}

array<ll, 2> get(int l, int r, int p, int k){
  if(r <= p){
    return array<ll,2>{T[k][0], T[k][1]};
  }
  int mid = l+r>>1;
  if(p <= mid) return get(l, mid, p, k<<1);
  auto R = get(mid + 1, r, p, k<<1|1);
  if(R[0] >= T[k<<1][1]){
    return array<ll,2>{T[k<<1][0] + R[0] - T[k<<1][1], R[1]};
  }
  return array<ll,2>{T[k<<1][0], T[k<<1][1] - R[0] + R[1]};
}

array<ll, 2> get2(int l, int r, int p, int k, ll val){
  int mid = l+r>>1;
  if(r <= p){
    if(TT[k] < val){ // if not enough
      return array<ll, 2>{TT[k], T[k][2]};
    }
    if(l == r){ // leaf case, end of the search
      assert(TT[k] >= val);
      return {TT[k], T[k][2]}; // result we want
    }
    if(TT[k<<1|1] >= val){ // right is enough
      return get2(mid+1, r, p, k<<1|1, val);
    }
    // descend left again
    auto res = get2(l, mid, p, k<<1, val - TT[k<<1|1]);
    return {res[0] + TT[k<<1|1], res[1]};
  }
  if(p <= mid) return get2(l, mid, p, k<<1, val);
  auto R = get2(mid+1, r, p, k<<1|1, val);
  if(R[0] >= val) return R;
  auto res = get2(l, mid, p, k<<1, val - R[0]);
  return {res[0] + R[0], res[1]};
}

void solve(){
  cin >> n >> m >> q;
  vector<ll> ans(q + 1);
  int qq = 0;
  for(int i = 1; i <= q; ++i){
    int tp; cin >> tp;
    if(tp == 1){
      ll l, r, c, k; cin >> l >> r >> c >> k;
      Q[l].pb({i, c, k});
      Q[r + 1].pb({-i, c, k});
    }else if(tp == 2){
      ll l, r, k; cin >> l >> r >> k;
      Q[l].pb({i, -1, k});
      Q[r + 1].pb({-i, -1, k});
    }else{
      ll a, b; cin >> a >> b;
      QQ[a].pb({i, b, ++qq});
    }
  }

  for(int i = 1; i <= 4*q; ++i) T[i] = {0, 0, -1}, TT[i] = 0;

  for(int i = 1; i <= n; ++i){
    for(auto [t, c, k]: Q[i]){
      if(c == -1){
        if(t < 0){
          rem(1, q, -t, 1, c, k);
        }else{
          add(1, q, t, 1, c, -k);
        }
      }else{
        if(t < 0){
          rem(1, q, -t, 1, c, k);
        }else{
          add(1, q, t, 1, c, k);
        }
      }
    }
    for(auto [t, k, idx]: QQ[i]){
      auto val = get(1, q, t, 1);
      ans[idx] = val[1] < k ? 0ll : get2(1, q, t, 1, val[1] - k + 1)[1];
    }
  }

  for(int i = 1; i <= qq; ++i){
    cout << ans[i] << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• 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