Submission #1189207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189207		epicci23	푸드 코트 (JOI21_foodcourt)	C++20	100 / 100	358 ms	54100 KiB

foodcourt

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5e4 + 5;
const int LOG = 20;

struct Info{
  int mn,ind,lazy;
};

Info T[4 * N], BOS;
int fw[N][2], ans[N];

void push(int rt,int l,int r){
  if(!T[rt].lazy) return;
  int u = T[rt].lazy;
  T[rt].lazy = 0;
  T[rt].mn += u;
  if(l == r) return;
  T[rt * 2].lazy += u, T[rt * 2 + 1].lazy += u;
}

Info merge(Info a,Info b){
  if(a.ind == -1) return b;
  if(b.ind == -1) return a;
  Info res;
  res.lazy = 0;
  res.ind = (a.mn <= b.mn ? a.ind : b.ind);
  res.mn = min(a.mn, b.mn);
  return res;
}

void build(int rt,int l,int r){
  if(l == r){
  	T[rt].ind = l;
  	T[rt].lazy = 0;
  	T[rt].mn = 0;
  	return;
  }
  int mid = (l + r) / 2;
  build(rt * 2, l, mid), build(rt * 2 + 1, mid + 1, r);
  T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);
}

void upd(int rt,int l,int r,int gl,int gr,int val){
  push(rt, l, r);
  if(r < gl || l > gr) return;
  if(l >= gl && r <= gr){
  	T[rt].lazy += val;
  	push(rt, l, r);
  	return;
  }
  int mid = (l + r) / 2;
  upd(rt * 2, l, mid, gl, gr, val), upd(rt * 2 + 1, mid + 1, r, gl, gr, val);
  T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);
}

Info query(int rt,int l,int r,int gl,int gr){
  push(rt, l, r);
  if(r < gl || l > gr) return BOS;
  if(l >= gl && r <= gr) return T[rt];
  int mid = (l + r) / 2;
  return merge(query(rt * 2, l, mid, gl, gr), query(rt * 2 + 1, mid + 1 ,r ,gl ,gr));
}

void add(int ind,int val,int t){
  for(;ind<N;ind += ind & -ind) fw[ind][t] += val;
}

int get(int ind,int t,int res = 0){
  for(;ind;ind -= ind & -ind) res += fw[ind][t];
  return res;
}

int bs(int k,int res = 0,int p = 0){
  for(int bit = LOG - 1; bit >= 0; bit--){
   if(p + (1<<bit) >= N) continue;
   if(fw[p + (1<<bit)][0] < k){
     k -= fw[p + (1<<bit)][0];
     p += (1<<bit);
   }
  }

  return p + 1;
}

void _(){	
  int n,m,q;
  cin >> n >> m >> q;
  
  build(1,0,q);
  int ptr = 0;

  BOS.ind = -1;
  BOS.lazy = 0;
  BOS.mn = 0;

  vector<int> Open[N],Close[N],Sor[N];
  array<int,4> op[N];

  for(int i=1;i<=q;i++){
  	int d;
  	cin >> d;
  	if(d == 1){
  	  int l,r,k,id;
  	  cin >> l >> r >> id >> k;
  	  op[i] = {l, r, k, id};
  	  Open[l].push_back(i);
  	  Close[r+1].push_back(i);
  	}
  	else if(d == 2){
      int l,r,k;
      cin >> l >> r >> k;
      op[i] = {l, r, k, -1};
      Open[l].push_back(i);
      Close[r+1].push_back(i);
  	}
  	else{
      int a,k;
      cin >> a >> k;
      op[i] = {-1, ptr++, a, k};	
      Sor[a].push_back(i);
  	}
  }


  for(int i=1;i<=n;i++){
  	for(int ind : Open[i]){
  	  if(op[ind][3] == -1){
       upd(1,0,q,ind,q,-op[ind][2]);
       add(ind, op[ind][2], 1);
      }
      else{
       upd(1,0,q,ind,q,op[ind][2]);
       add(ind, op[ind][2], 0);
      }
  	}
    
    for(int ind : Close[i]){
  	  if(op[ind][3] == -1){
       upd(1,0,q,ind,q,op[ind][2]);
       add(ind, -op[ind][2], 1);
      }
      else{
       upd(1,0,q,ind,q,-op[ind][2]);
       add(ind, -op[ind][2], 0);
      }
  	}

  	for(int ind : Sor[i]){
  	  //cout << "bak : " << i << ' ' << ind << '\n';
      Info X = query(1,0,q,0,ind);
      if(X.mn >= 0) X.ind = 0;
      
      //cout << X.ind << ' ' << X.mn << '\n';

      int xd = get(X.ind, 0);
      xd += get(ind, 1) - get(X.ind, 1);
      xd += op[ind][3];

      //cout << "neymis : " << xd << '\n';

      if(xd > get(ind, 0) || get(ind, 0) == 0){
      	ans[op[ind][1]] = 0;
      	continue;
      }

      int hangi = bs(xd);

      //cout << "hangi : " << ind << ' ' << hangi << '\n';

      if(op[hangi][3] == -1 || op[hangi][0] == -1 || hangi > q || get(hangi, 0) < xd) ans[op[ind][1]] = 0;
      else ans[op[ind][1]] = op[hangi][3]; 
  	}
  }

  for(int i=0;i<ptr;i++) cout << ans[i] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  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