oj.uz

Submission #91139

# Submission time Handle Problem Language Result Execution time Memory
91139 2018-12-26T10:56:04 Z Milki Krave (COI14_krave) C++14
100 / 100
 938 ms 120856 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int off = 1 << 17;
const int INF = 1e9;

int X, Y, n;

struct rectangle{
  int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  rectangle(){};
  rectangle(int _x1, int _y1, int _x2, int _y2){
    x1 = _x1; y1 = _y1; x2 = _x2, y2 = _y2;
  }
  ll calc(){
    return (ll)(x2 - x1) * (y2 - y1);
  }
  friend bool operator < (const rectangle A, const rectangle B){
    if(A.x2 != B.x2) return A.x2 < B.x2;
    return A.y2 < B.y2;
  }
};

struct Tournament{
  set <int> t[2 * off];

  void update(int x, int lo, int hi, int a, int b, int val){
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b) { t[x].insert(val); return; }

    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b, val);
    update(x * 2 + 1, mid, hi, a, b, val);
  }

  int get(int x, int bounds){
    x += off;
    int ret = INF;
    for(; x > 0; x >>= 1){
      auto it = t[x].lower_bound(bounds);
      if(it != t[x].end()){
        ret = min(ret, *it);
        //cout << *it << " lol\n";
      }
    }
    return ret;
  }
} vertical, horizontal;

set<rectangle> S;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> X >> Y >> n;

  horizontal.update(1, 0, off, 0, X + 1, Y); // horizontalno od 0 do X presijeca pravac Y
  horizontal.update(1, 0, off, 0, X + 1, 0);
  vertical.update(1, 0, off, 0, Y + 1, 0);
  vertical.update(1, 0, off, 0, Y + 1, X);
  S.insert(rectangle(0, 0, X, Y));

  REP(i, n){
    int x, y, d; cin >> x >> y >> d;
    int x2 = vertical.get(y, x);
    //cout << "evo ga" _ i _ horizontal.get(3, 3) << " evo ga\n";
    //cout << "\n sad ce gornji: \n";
    int y2 = horizontal.get(x, y);
    //cout << "x2 y2" _ x2 _ y2 << " x y " << x _ y << "\n";
    auto xd = S.lower_bound(rectangle(-1, -1, x2, y2));

    rectangle it = *xd;
    //cout << it.x1 _ it.y1 _ x2 _ y2 << " x2 y2\n";
    S.erase(xd);
    rectangle A, B;
    if(d == 1){
      A = rectangle(it.x1, it.y1, x2, y);
      B = rectangle(it.x1, y, x2, y2);
      horizontal.update(1, 0, off, it.x1, x2 + 1, y);
      //cout << "od " << it.x1 _ "do " << x2 << " je " << y << "\n";
    }
    else{
      A = rectangle(it.x1, it.y1, x, y2);
      B = rectangle(x, it.y1, x2, y2);
      vertical.update(1, 0, off, it.y1, y2 + 1, x);
    }
    cout << min(A.calc(), B.calc()) _ max(A.calc(), B.calc()) << "\n";
    S.insert(A); S.insert(B);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25080 KB Output is correct
2 Correct 23 ms 25116 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25644 KB Output is correct
2 Correct 28 ms 26084 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 42360 KB Output is correct
2 Correct 239 ms 55484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 55484 KB Output is correct
2 Correct 284 ms 57488 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 57488 KB Output is correct
2 Correct 430 ms 80104 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 80104 KB Output is correct
2 Correct 502 ms 82040 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 82040 KB Output is correct
2 Correct 565 ms 87952 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 87952 KB Output is correct
2 Correct 361 ms 87952 KB Output is correct
3 Correct 379 ms 87952 KB Output is correct
4 Correct 513 ms 95588 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 95588 KB Output is correct
2 Correct 363 ms 95588 KB Output is correct
3 Correct 378 ms 95588 KB Output is correct
4 Correct 879 ms 115948 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 115948 KB Output is correct
2 Correct 271 ms 115948 KB Output is correct
3 Correct 318 ms 115948 KB Output is correct
4 Correct 642 ms 120856 KB Output is correct