Submission #1263826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263826		minhpk	Food Court (JOI21_foodcourt)	C++20	100 / 100	276 ms	105976 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,t;
int z[1000005];
vector<pair<int,int>> del[1000005],add[1000005],q[1000005];
struct node{
     int val,min1;
};
struct st{
      node f[4000005];
      void build(){
           for (int i=1;i<=4*t;i++){
                f[i]={0,0};
           }
      }
      void update(int id,int l,int r,int pos,int val){
           if (l==r){
              f[id].val=val;
              f[id].min1=min(0LL,val);
              return;
           }
           int mid=(l+r)/2;
           if (pos<=mid){
               update(id*2,l,mid,pos,val);
           }else{
               update(id*2+1,mid+1,r,pos,val);
           }
           f[id].val=f[id*2].val+f[id*2+1].val;
           f[id].min1=min(f[id*2].min1,f[id*2].val+f[id*2+1].min1);
      }
      node get(int id,int l,int r,int x,int y){
          if (x>r || y<l){
              return {0,0};
          }
          if (l>=x && y>=r){
              return f[id];
          }
          int mid=(l+r)/2;
          node pre=get(id*2,l,mid,x,y);
          node pre1=get(id*2+1,mid+1,r,x,y);
          return {pre.val+pre1.val,min(pre.min1,pre.val+pre1.min1)};
      }
      int get(int id,int l,int r,int val){
          if (l==r){
              return l;
          }
          int mid=(l+r)/2;
          if (val<=f[id*2].val){
              return get(id*2,l,mid,val);
          }else{
              return get(id*2+1,mid+1,r,val-f[id*2].val);
          }
      }
};
st f,f1;
vector <pair<int,int>> ans;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> t;
    for (int i=1;i<=t;i++){
         int c;
         cin >> c;
         if (c==1){
             int l,r,k;
             cin >> l >> r >> z[i] >> k;
             add[l].push_back({i,k});
             add[r+1].push_back({i,0});

         }else if (c==2){
             int l,r,k;
             cin >> l >> r >> k;
             del[l].push_back({i,-k});
             del[r+1].push_back({i,0});
         }else{
             int x,y;
             cin >> x >> y;
             q[x].push_back({i,y});
         }
    }
    for (int i=1;i<=a;i++){
         for (auto p:add[i]){
              f.update(1,1,t,p.first,p.second);
              f1.update(1,1,t,p.first,p.second);
         }
         for (auto p:del[i]){
              f.update(1,1,t,p.first,p.second);
         }
         for (auto p:q[i]){
              node pre=f.get(1,1,t,1,p.first);
              node pre1=f1.get(1,1,t,1,p.first);
              int pos=pre1.val-pre.val+pre.min1+p.second;
              if (pos>pre1.val){
                  ans.push_back({p.first,0});
              }else{
                  int col=z[f1.get(1,1,t,pos)];
                  ans.push_back({p.first,col});
              }
         }
    }
    sort(ans.begin(),ans.end());
    for (auto p:ans){
         cout << p.second << "\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