| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 667856 |
2022-12-02T07:20:53 Z |
BlackJack |
Krave (COI14_krave) |
C++14 |
|
806 ms |
84208 KB |
#include<bits/stdc++.h>
using namespace std;
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if(sizeof...(t)) cerr << ", ";
DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
void setIO(string NAME = "") {
cin.tie(0)->sync_with_stdio(0);
if(sz(NAME)) {
freopen((NAME + ".inp").c_str(),"r",stdin);
freopen((NAME + ".out").c_str(),"w",stdout);
}
}
tcT> bool ckmin(T&a, const T&b) {
return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
return b > a ? a=b,1 : 0; }
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int MX = 1e5+5;
struct SegTree {
set<int> seg[MX*4 + 7];
int N;
void init(int _SZ) {
N = _SZ;
}
void addPoint(int l, int r, int pos, int ind, int L, int R) {
if(l > R || r < L) return;
if(l <= L && R <= r) {
seg[ind].insert(pos);
return;
}
int mid = (L + R) >> 1;
addPoint(l, r, pos, ind<<1, L, mid);
addPoint(l, r, pos, ind<<1|1, mid+1, R);
}
void addPoint(int l, int r, int pos) {
addPoint(l, r, pos, 1, 0, N);
}
int query(int pos, int val, int ind, int L, int R) {
if(R < pos || pos < L) return -1;
auto it = seg[ind].upper_bound(val);
int res = -1;
if(it != seg[ind].begin()) {
it--;
res = *it;
}
if(L == R) return res;
int mid = (L + R) >> 1;
if(pos <= mid) ckmax(res, query(pos, val, ind<<1, L, mid));
else ckmax(res, query(pos, val, ind<<1|1, mid+1, R));
return res;
}
int query(int pos, int val) {
return query(pos, val, 1, 0, N);
}
};
struct Rect {
int xl, yl, xr, yr;
ll getArea() { return 1LL*(xr - xl)*(yr - yl); }
Rect(int _xl = 0, int _yl = 0, int _xr = 0, int _yr = 0) {
xl = _xl;
yl = _yl;
xr = _xr;
yr = _yr;
}
bool operator<(const Rect&rhs) const {
if(xl != rhs.xl) return xl < rhs.xl;
return yl < rhs.yl;
}
};
int A, B;
int N;
SegTree stX, stY;
set<Rect> s;
void solve() {
cin >> A >> B;
stY.init(A);
stX.init(B);
stY.addPoint(0, A, 0);
stX.addPoint(0, B, 0);
s.insert(Rect(0, 0, A, B));
cin >> N;
while(N-- > 0) {
int x, y, dir;
cin >> x >> y >> dir;
int rect_y = stY.query(x, y), rect_x = stX.query(y, x);
assert(rect_y >= 0 && rect_x >= 0);
auto it = s.lower_bound(Rect(rect_x, rect_y, -1, -1));
int xl = it->xl, yl = it->yl, xr = it->xr, yr = it->yr;
s.erase(it);
Rect newA, newB;
if(dir == 1) {
newA = Rect(xl, yl, xr, y);
newB = Rect(xl, y, xr, yr);
stY.addPoint(xl, xr, y);
}
else {
newA = Rect(xl, yl, x, yr);
newB = Rect(x, yl, xr, yr);
stX.addPoint(yl, yr, x);
}
cout << min(newA.getArea(), newB.getArea()) << " " << max(newA.getArea(), newB.getArea()) << nl;
s.insert(newA);
s.insert(newB);
}
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
Compilation message
krave.cpp: In function 'void setIO(std::string)':
krave.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((NAME + ".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
krave.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((NAME + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
37972 KB |
Output is correct |
| 2 |
Correct |
21 ms |
37884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
38340 KB |
Output is correct |
| 2 |
Correct |
24 ms |
38732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
45844 KB |
Output is correct |
| 2 |
Correct |
123 ms |
47580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
45824 KB |
Output is correct |
| 2 |
Correct |
136 ms |
48960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
45872 KB |
Output is correct |
| 2 |
Correct |
151 ms |
50508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
54532 KB |
Output is correct |
| 2 |
Correct |
354 ms |
71116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
795 ms |
72080 KB |
Output is correct |
| 2 |
Correct |
417 ms |
76492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
774 ms |
71276 KB |
Output is correct |
| 2 |
Correct |
315 ms |
79272 KB |
Output is correct |
| 3 |
Correct |
164 ms |
51656 KB |
Output is correct |
| 4 |
Correct |
366 ms |
79056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
806 ms |
72304 KB |
Output is correct |
| 2 |
Correct |
361 ms |
83272 KB |
Output is correct |
| 3 |
Correct |
169 ms |
51880 KB |
Output is correct |
| 4 |
Correct |
375 ms |
81796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
72700 KB |
Output is correct |
| 2 |
Correct |
256 ms |
72992 KB |
Output is correct |
| 3 |
Correct |
157 ms |
51968 KB |
Output is correct |
| 4 |
Correct |
392 ms |
84208 KB |
Output is correct |
