oj.uz

Submission #999116

# Submission time Handle Problem Language Result Execution time Memory
999116 2024-06-15T06:55:42 Z huutuan Pyramid Base (IOI08_pyramid_base) C++14
80 / 100
 5000 ms 153340 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Node{
   int val, lazy;
   Node (int _val=0){
      val=_val, lazy=0;
   }
   Node operator+(const Node &a){
      return Node(min(val, a.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]=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=5e5+10;
int m, n, p, q;
Rect a[N], b[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;
      vector<pair<pair<int, int>, pair<int, int>>> events;
      for (int i=1; i<=n; ++i){
         events.push_back({{max(1ll, a[i].x1-mid+1), a[i].z}, {max(1ll, a[i].y1-mid+1), a[i].y2}});
         events.push_back({{a[i].x2+1, -a[i].z}, {max(1ll, a[i].y1-mid+1), a[i].y2}});
      }
      sort(events.begin(), events.end());
      bool check=0;
      for (int i=0; i<(int)events.size(); ++i){
         st.update(1, 1, q, events[i].second.first, events[i].second.second, events[i].first.second);
         if (i==(int)events.size()-1 || events[i].first.first!=events[i+1].first.first){
            if (events[i].first.first+mid-1<=p){
               check|=st.get(1, 1, q, 1, q-mid+1)<=m;
            }
         }
      }
      if (check) l=mid+1;
      else r=mid-1;
   }
   cout << r << '\n';
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39512 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 40316 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45916 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 102236 KB Output is correct
2 Correct 34 ms 102236 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102232 KB Output is correct
2 Correct 26 ms 102276 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 41028 KB Output is correct
2 Correct 58 ms 41144 KB Output is correct
3 Correct 48 ms 41172 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 47792 KB Output is correct
2 Correct 249 ms 48244 KB Output is correct
3 Correct 210 ms 48204 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 105540 KB Output is correct
2 Correct 54 ms 43352 KB Output is correct
3 Correct 179 ms 105960 KB Output is correct
4 Correct 477 ms 106168 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 106396 KB Output is correct
2 Correct 530 ms 106568 KB Output is correct
3 Correct 386 ms 106644 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 106136 KB Output is correct
2 Correct 700 ms 107004 KB Output is correct
3 Correct 690 ms 107012 KB Output is correct
4 Correct 721 ms 107016 KB Output is correct
5 Correct 694 ms 107180 KB Output is correct
6 Correct 428 ms 107088 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4627 ms 135132 KB Output is correct
2 Correct 1597 ms 81660 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5008 ms 153340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5034 ms 152084 KB Time limit exceeded
2 Halted 0 ms 0 KB -