Submission #971476

#	Time	Username	Problem	Language	Result	Execution time	Memory
971476		huutuan	Food Court (JOI21_foodcourt)	C++14	100 / 100	313 ms	66356 KiB

foodcourt

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int inf=1e18;

struct Node{
   int x, y;
   Node (){
      x=-inf, y=0;
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int x, int y){
      t[k].x=max(x, t[k].x+y);
      t[k].y+=y;
   }
   void push(int k){
      if (t[k].x!=-inf || t[k].y!=0){
         apply(k<<1, t[k].x, t[k].y);
         apply(k<<1|1, t[k].x, t[k].y);
         t[k]=Node();
      }
   }
   void update(int k, int l, int r, int L, int R, int x, int y){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, x, y);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, x, y);
      update(k<<1|1, mid+1, r, L, R, x, y);
   }
   int get(int k, int l, int r, int pos){
      if (l==r) return max(t[k].x, t[k].y);
      push(k);
      int mid=(l+r)>>1;
      if (pos<=mid) return get(k<<1, l, mid, pos);
      return get(k<<1|1, mid+1, r, pos);
   }
} st;

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   void update(int l, int r, int val){
      update(l, val);
      if (r<n) update(r+1, -val);
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
   int lower_bound(int val){
      int ans=0;
      for (int i=17; i>=0; --i){
         if (ans+(1<<i)<=n && val>t[ans+(1<<i)]){
            ans+=1<<i;
            val-=t[ans];
         }
      }
      return ans+1;
   }
} bit1, bit2;

struct Query{
   int l, r, c, k, i;
   Query (int _l=0, int _r=0, int _c=0, int _k=0, int _i=0){
      l=_l, r=_r, c=_c, k=_k, i=_i;
   }
};

const int N=25e4+10;
int n, m, q, ans[N];
Query a[N];
vector<pair<int, int>> v[N];
vector<Query> event[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m >> q;
   st.init(n);
   bit1.init(n);
   int n1=0, n2=0;
   for (int i=1; i<=q; ++i){
      int type; cin >> type;
      if (type==1){
         int l, r, c, k; cin >> l >> r >> c >> k;
         ++n1;
         a[n1]=Query(l, r, c, k, n1);
         st.update(1, 1, n, l, r, -inf, k);
         bit1.update(l, r, k);
      }else if (type==2){
         int l, r, k; cin >> l >> r >> k;
         st.update(1, 1, n, l, r, 0, -k);
      }else{
         int x, y; cin >> x >> y;
         int sz=st.get(1, 1, n, x);
         int r=bit1.get(x);
         int l=r-sz;
         ++n2;
         if (y<=sz) v[x].emplace_back(l+y-1, n2);
      }
   }
   bit2.init(n1);
   for (int i=1; i<=n1; ++i) event[a[i].l].push_back(a[i]), event[a[i].r+1].push_back(a[i]);
   for (int i=1; i<=n; ++i){
      for (auto &j:event[i]){
         if (j.l==i){
            bit2.update(j.i, j.k);
         }else{
            bit2.update(j.i, -j.k);
         }
      }
      for (auto &j:v[i]){
         ans[j.second]=a[bit2.lower_bound(j.first+1)].c;
      }
   }
   for (int i=1; i<=n2; ++i) cout << ans[i] << '\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