| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125091 |
2019-07-04T15:08:38 Z |
abacaba |
Krave (COI14_krave) |
C++14 |
|
770 ms |
262148 KB |
#include <bits/stdc++.h>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define endl '\n'
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
#define int long long
const int N = 1e5 + 15;
int w, h, n, m, k, a[N];
vector <int> addcol[N << 2], addrow[N << 2];
set <int> row[N << 2], col[N << 2];
inline void pushcol(int v) {
while(!addcol[v].empty()) {
if(v < (N << 1)) {
addcol[v << 1].pb(addcol[v].back());
addcol[v << 1 | 1].pb(addcol[v].back());
col[v << 1].insert(addcol[v].back());
col[v << 1 | 1].insert(addcol[v].back());
}
addcol[v].ppb();
}
}
inline void pushrow(int v) {
while(!addrow[v].empty()) {
if(v < (N << 1)) {
addrow[v << 1].pb(addrow[v].back());
addrow[v << 1 | 1].pb(addrow[v].back());
row[v << 1].insert(addrow[v].back());
row[v << 1 | 1].insert(addrow[v].back());
}
addrow[v].ppb();
}
}
void multiupdatecol(int v, int tl, int tr, int l, int r, int val) {
if(tl > r || tr < l || l > r)
return;
pushcol(v);
if(tl >= l && tr <= r) {
col[v].insert(val);
addcol[v].pb(val);
return;
}
int mid = tl + tr >> 1;
multiupdatecol(v << 1, tl, mid, l, r, val);
multiupdatecol(v << 1 | 1, mid + 1, tr, l, r, val);
}
void multiupdaterow(int v, int tl, int tr, int l, int r, int val) {
if(tl > r || tr < l || l > r)
return;
pushrow(v);
if(tl >= l && tr <= r) {
row[v].insert(val);
addrow[v].pb(val);
return;
}
int mid = tl + tr >> 1;
multiupdaterow(v << 1, tl, mid, l, r, val);
multiupdaterow(v << 1 | 1, mid + 1, tr, l, r, val);
}
int getcol(int v, int tl, int tr, int pos, int x, bool islower) {
pushcol(v);
if(tl == tr) {
if(islower)
return *(--col[v].upper_bound(x));
return *col[v].upper_bound(x);
}
int mid = tl + tr >> 1;
if(pos <= mid)
return getcol(v << 1, tl, mid, pos, x, islower);
return getcol(v << 1 | 1, mid + 1, tr, pos, x, islower);
}
int getrow(int v, int tl, int tr, int pos, int x, bool islower) {
pushrow(v);
if(tl == tr) {
if(islower)
return *(--row[v].upper_bound(x));
return *row[v].upper_bound(x);
}
int mid = tl + tr >> 1;
if(pos <= mid)
return getrow(v << 1, tl, mid, pos, x, islower);
return getrow(v << 1 | 1, mid + 1, tr, pos, x, islower);
}
#undef int
int main() {
#define int long long
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> w >> h >> n;
multiupdatecol(1, 1, N - 1, 1, N - 1, 0);
multiupdatecol(1, 1, N - 1, 1, N - 1, w);
multiupdaterow(1, 1, N - 1, 1, N - 1, 0);
multiupdaterow(1, 1, N - 1, 1, N - 1, h);
for(int i = 1; i <= n; ++i) {
int x, y, d;
cin >> x >> y >> d;
if(d == 1) {
int x2 = getcol(1, 1, N - 1, y, x, 0);
int x1 = getcol(1, 1, N - 1, y, x, 1);
int y2 = getrow(1, 1, N - 1, x, y, 0);
int y1 = getrow(1, 1, N - 1, x, y, 1);
int area1 = abs(y - y1) * abs(x2 - x1);
int area2 = abs(y - y2) * abs(x2 - x1);
if(area2 < area1)
swap(area2, area1);
cout << area1 << ' ' << area2 << endl;
multiupdaterow(1, 1, N - 1, x1, x2, y);
}
else {
int x2 = getcol(1, 1, N - 1, y, x, 0);
int x1 = getcol(1, 1, N - 1, y, x, 1);
int y2 = getrow(1, 1, N - 1, x, y, 0);
int y1 = getrow(1, 1, N - 1, x, y, 1);
int area1 = abs(y2 - y1) * abs(x - x1);
int area2 = abs(y2 - y1) * abs(x2 - x);
if(area2 < area1)
swap(area2, area1);
cout << area1 << ' ' << area2 << endl;
multiupdatecol(1, 1, N - 1, y1, y2, x);
}
}
return 0;
}
Compilation message
krave.cpp: In function 'void multiupdatecol(long long int, long long int, long long int, long long int, long long int, long long int)':
krave.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
krave.cpp: In function 'void multiupdaterow(long long int, long long int, long long int, long long int, long long int, long long int)':
krave.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
krave.cpp: In function 'long long int getcol(long long int, long long int, long long int, long long int, long long int, bool)':
krave.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
krave.cpp: In function 'long long int getrow(long long int, long long int, long long int, long long int, long long int, bool)':
krave.cpp:102:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
60536 KB |
Output is correct |
| 2 |
Correct |
61 ms |
59128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
94452 KB |
Output is correct |
| 2 |
Runtime error |
643 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
685 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
687 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
695 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
770 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
725 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
756 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
710 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
739 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
