Submission #1189137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189137		mychecksedad	Food Court (JOI21_foodcourt)	C++20	21 / 100	235 ms	89092 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;


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

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};
  }
}

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};
    }else{
      T[k] = {0, val, c};
    }
    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};
    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]};
}

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};

  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);
      // cout << k << ' ' << val[1] << ' ' << idx << '\n';
      ans[idx] = val[1] < k ? 0ll : 1LL;//get2(1, q, t, 1, b);
    }
  }

  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: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 21 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11