Submission #120964

#TimeUsernameProblemLanguageResultExecution timeMemory
120964luciocfKrave (COI14_krave)C++14
0 / 100
3120 ms99472 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; typedef pair<int, int> pii; typedef long long ll; struct node { set<pii> st; } tree[2][4*maxn]; int n, A, B; bool ok(int node, int x, bool q) { set<pii>::iterator it = tree[q][node].st.lower_bound({x+1, 0}); if (it == tree[q][node].st.begin()) return false; --it; return (it->first <= x && it->second >= x); } void upd(int node, int l, int r, int pos, pii pp, bool q) { tree[q][node].st.insert(pp); if (l == r) return; int mid = (l+r)>>1; if (pos <= mid) upd(2*node, l, mid, pos, pp, q); else upd(2*node+1, mid+1, r, pos, pp, q); } // rightmost in range [a, b] int query1(int node, int l, int r, int a, int b, int x, bool q) { if (l > r) return -1; if (!ok(node, x, q)) return -1; if (l == r) return l; int mid = (l+r)>>1; if (mid+1 > b) return query1(2*node, l, mid, a, b, x, q); int ans = query1(2*node+1, mid+1, r, a, b, x, q); if (ans == -1) ans = query1(2*node, l, mid, a, b, x, q); return ans; } // leftmost in range [a, b] int query2(int node, int l, int r, int a, int b, int x, bool q) { if (l > r) return -1; if (!ok(node, x, q)) return -1; if (l == r) return l; int mid = (l+r)>>1; if (mid < a) return query2(2*node+1, mid+1, r, a, b, x, q); int ans = query2(2*node, l, mid, a, b, x, q); if (ans == -1) ans = query2(2*node+1, mid+1, r, a, b, x, q); return ans; } int main(void) { scanf("%d %d %d", &A, &B, &n); for (int i = 1; i <= n; i++) { int x, y, d; scanf("%d %d %d", &x, &y, &d); if (d == 1) { int l = query1(1, 1, A, 1, x-1, y, 0); int r = query2(1, 1, A, x+1, A, y, 0); if (l == -1) l = 0; if (r == -1) r = A; int h1 = query2(1, 1, B, y+1, B, l, 1); int h2 = query1(1, 1, B, 1, y-1, l, 1); if (h1 == -1) h1 = B; if (h2 == -1) h2 = 0; ll area1 = 1ll*(r-l)*(h1-y), area2 = 1ll*(r-l)*(y-h2); printf("%lld %lld\n", min(area1, area2), max(area1, area2)); upd(1, 1, B, y, {l, r}, 1); } else { int l = query1(1, 1, B, 1, y-1, x, 1); int r = query2(1, 1, B, y+1, B, x, 1); if (l == -1) l = 0; if (r == -1) r = B; int h1 = query2(1, 1, A, x+1, A, l, 0); int h2 = query1(1, 1, A, 1, x-1, l, 0); if (h1 == -1) h1 = A; if (h2 == -1) h2 = 0; ll area1 = 1ll*(r-l)*(h1-x), area2 = 1ll*(r-l)*(x-h2); printf("%lld %lld\n", min(area1, area2), max(area1, area2)); upd(1, 1, A, x, {l, r}, 0); } } }

Compilation message (stderr)

krave.cpp: In function 'int main()':
krave.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &A, &B, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
krave.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...