Submission #999124

#	Time	Username	Problem	Language	Result	Execution time	Memory
999124		huutuan	Pyramid Base (IOI08_pyramid_base)	C++14	63 / 100	5070 ms	190392 KiB

pyramid_base

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Node{
   int val, lazy;
   Node (int _val=0){
      val=_val, lazy=0;
   }
   void merge(const Node &tl, const Node &tr){
      val=min(tl.val, tr.val);
   }
};

struct SegmentTree{
   vector<Node> t;
   int n;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int val){
      t[k].val+=val;
      t[k].lazy+=val;
   }
   void push(int k){
      if (t[k].lazy){
         apply(k<<1, t[k].lazy);
         apply(k<<1|1, t[k].lazy);
         t[k].lazy=0;
      }
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return 1e18;
      if (L<=l && r<=R) return t[k].val;
      push(k);
      int mid=(l+r)>>1;
      return min(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} st;

struct Rect{
   int x1, y1, x2, y2, z;
   Rect(){ x1=0, y1=0, x2=0, y2=0, z=0; }
};

const int N=1e6+10;
int m, n, p, q;
Rect a[N], b[N];
vector<pair<int, pair<int, int>>> events[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> p >> q >> m >> n;
   st.init(q);
   for (int i=1; i<=n; ++i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].z;
   int l=1, r=min(p, q);
   while (l<=r){
      int mid=(l+r)>>1;
      for (int i=1; i<=n; ++i){
         events[max(1ll, a[i].x1-mid+1)].push_back({a[i].z, {max(1ll, a[i].y1-mid+1), a[i].y2}});
         events[a[i].x2+1].push_back({-a[i].z, {max(1ll, a[i].y1-mid+1), a[i].y2}});
      }
      bool check=0;
      for (int i=1; i<=q+1; ++i){
         for (auto &j:events[i]) st.update(1, 1, q, j.second.first, j.second.second, j.first);
         if (i+mid-1<=p){
            check|=st.get(1, 1, q, 1, q-mid+1)<=m;
         }
         events[i].clear();
         events[i].shrink_to_fit();
      }
      if (check) l=mid+1;
      else r=mid-1;
   }
   cout << r << '\n';
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 0 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10