제출 #706523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706523		Pety	푸드 코트 (JOI21_foodcourt)	C++14	100 / 100	804 ms	43300 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin ("text.in");
ofstream fout ("text.out");

const int N = 250002;

struct node {
  ll min1, min2;
  ll fr;
} aint[4*N];

ll lazy[4*N]; 

int a[N], b[N];
ll c[N], k[N], cnt[N], answer[N];

node merge (node a, node b) {
  node c;
  if (a.min1 == b.min1) {
    c.min1 = a.min1;
    c.fr = a.fr + b.fr;
    c.min2 = min(a.min2, b.min2);
  }
  else if (a.min1 < b.min1) {
    c.min1 = a.min1;
    c.fr = a.fr;
    c.min2 = min(a.min2, b.min1);
  }
  else {
    c.min1 = b.min1;
    c.fr = b.fr;
    c.min2 = min(b.min2, a.min1);
  }
  return c;
}

void push_add(int nod, ll x) {
  aint[nod].min1 += x;
  if (aint[nod].min2 != 1e18)
    aint[nod].min2 += x;
  lazy[nod] += x;
}

void push_max (int nod, ll k) {
  aint[nod].min1 = max(aint[nod].min1, k);
}


void push_lazy (int nod, int st, int dr) {
  if (st == dr)
    return;
  push_add(2 * nod, lazy[nod]);
  push_add(2 * nod + 1, lazy[nod]);
  lazy[nod] = 0;
  push_max(2 * nod, aint[nod].min1);
  push_max(2 * nod + 1, aint[nod].min1);
}

void update_chmax (int nod, int st, int dr, int a, int b, ll value) {
  push_lazy(nod, st, dr);
  if (a > b || b < st || a > dr || aint[nod].min1 >= value)
    return;
  if (a <= st && dr <= b && aint[nod].min2 > value) {
    push_max(nod, value);
    return;
  }
  int mid = (st + dr) / 2;
  update_chmax(2 * nod, st, mid, a, b, value);
  update_chmax(2 * nod + 1, mid + 1, dr, a, b, value);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
void update_sum (int nod, int st, int dr, int a, int b, ll x) {
  push_lazy(nod, st, dr);
  if (a > b || b < st || a > dr)
    return;
  if (a <= st && dr <= b)  {
    push_add(nod, x);
    return;
  }
  int mid = (st + dr) / 2;
  update_sum(2 * nod, st, mid, a, b, x);
  update_sum(2 * nod + 1, mid + 1, dr, a, b, x);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

void build (int nod, int st, int dr) {
  if (st == dr) {
    aint[nod].min1 = 0;
    aint[nod].min2 = 1e18;
    aint[nod].fr = 1;
    return;
  }
  int mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);

  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
ll query (int nod, int st, int dr, int a) {
  push_lazy(nod, st, dr);
  if (st == dr) {
    return aint[nod].min1;
  }
  int mid = (st + dr) / 2;
  if (a <= mid)
    return query(2 * nod, st, mid, a);
  else
    return query(2 * nod + 1, mid + 1, dr, a);
}

long long aint2[4*N];

void update (int nod, int st, int dr, int poz, ll x) {
  if (st == dr) {
    aint2[nod] = x;
    return;
  }
  int mid = (st + dr) / 2;
  if (poz <=mid)
    update(2 * nod, st, mid, poz, x);
  else
    update(2 * nod + 1, mid + 1, dr, poz, x);
  aint2[nod] = aint2[2 * nod] + aint2[2 * nod + 1];
}

int query2 (int nod, int st, int dr, ll x) {
  if (aint2[nod] < x)
    return 0;
  if (st == dr)
    return st;
  if (aint2[2*nod] < x)
    return query2(2 * nod + 1, (st + dr) / 2 + 1, dr, x - aint2[2 * nod]);
  else
    return query2(2 * nod, st, (st + dr) / 2, x);
}

ll query_sum (int nod, int st, int dr, int a, int b) {
  if (a > dr || b < st || a > b)
    return 0;
  if (a <= st && dr <= b)
    return aint2[nod];
  int mid = (st + dr) / 2;
  return query_sum(2 * nod, st, mid, a, b) + query_sum(2 * nod + 1, mid + 1, dr, a, b);
}

int n, m, q;

int main () 
{
  cin >> n >> m >> q;
  build(1, 1, n);
  vector<pair<int, pair<int, int>>>event;
  vector<int>idk(q + 2);
  for (int i = 1; i <= q; i++) {
    int type;
    cin >> type;
    if (type == 1) 
      cin >> a[i] >> b[i] >> c[i] >> k[i];
    if (type == 2) 
      cin >> a[i] >> b[i] >> k[i];
    if (type == 3) 
      cin >> a[i] >> k[i];
    if (type == 1) {
      event.push_back({a[i], {1, i}});
      event.push_back({b[i] + 1, {2, i}});
      update_sum(1, 1, n, a[i], b[i], k[i]);
    }
    if (type == 2) {
      update_sum(1, 1, n, a[i], b[i], -k[i]);
      update_chmax(1, 1, n, a[i], b[i], 0);
    }

    if (type == 3) {
      idk[i] = 1;
      cnt[i] = query(1, 1, n, a[i]);
      event.push_back({a[i], {3, i}});
    }
  }
  sort(event.begin(), event.end());
  for (auto it : event) {
    if (it.second.first == 1) {
      update(1, 1, q, it.second.second, k[it.second.second]);
    }
    if (it.second.first == 2) {
      update(1, 1, q, it.second.second, 0);
    }
    if (it.second.first == 3) {
      ll total = query_sum(1, 1, q, 1, it.second.second);
      if (cnt[it.second.second] < k[it.second.second]) {
        continue;
      }
      ll val = total - cnt[it.second.second] + k[it.second.second];
      int time = query2(1, 1, q, val);
      answer[it.second.second] = c[time];
    }
  }
  for (int i = 1; i <= q; i++)
    if (idk[i])
      cout << answer[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