Submission #91139

#	Time	Username	Problem	Language	Result	Execution time	Memory
91139		Milki	Krave (COI14_krave)	C++14	100 / 100	938 ms	120856 KiB

krave

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12