Submission #125093

#TimeUsernameProblemLanguageResultExecution timeMemory
125093abacabaKrave (COI14_krave)C++14
5 / 100
815 ms262148 KiB
#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> 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); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> w >> h >> n; multiupdatecol(1, 1, h, 1, h, 0); multiupdatecol(1, 1, h, 1, h, w); multiupdaterow(1, 1, w, 1, w, 0); multiupdaterow(1, 1, w, 1, w, h); for(int i = 1; i <= n; ++i) { int x, y, d; cin >> x >> y >> d; if(d == 1) { int x2 = getcol(1, 1, h, y, x, 0); int x1 = getcol(1, 1, h, y, x, 1); int y2 = getrow(1, 1, w, x, y, 0); int y1 = getrow(1, 1, w, x, y, 1); ll area1 = (ll)abs(y - y1) * abs(x2 - x1); ll area2 = (ll)abs(y - y2) * abs(x2 - x1); if(area2 < area1) swap(area2, area1); cout << area1 << ' ' << area2 << endl; multiupdaterow(1, 1, w, x1, x2, y); } else { int x2 = getcol(1, 1, h, y, x, 0); int x1 = getcol(1, 1, h, y, x, 1); int y2 = getrow(1, 1, w, x, y, 0); int y1 = getrow(1, 1, w, x, y, 1); ll area1 = (ll)abs(y2 - y1) * abs(x - x1); ll area2 = (ll)abs(y2 - y1) * abs(x2 - x); if(area2 < area1) swap(area2, area1); cout << area1 << ' ' << area2 << endl; multiupdatecol(1, 1, h, y1, y2, x); } } return 0; }

Compilation message (stderr)

krave.cpp: In function 'void multiupdatecol(int, int, int, int, int, int)':
krave.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
krave.cpp: In function 'void multiupdaterow(int, int, int, int, int, int)':
krave.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
krave.cpp: In function 'int getcol(int, int, int, int, int, bool)':
krave.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
krave.cpp: In function 'int getrow(int, int, int, int, int, bool)':
krave.cpp:100:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
#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...