Submission #114149

#TimeUsernameProblemLanguageResultExecution timeMemory
114149ShtefKrave (COI14_krave)C++14
10 / 100
1554 ms262144 KiB
#include <iostream> #include <set> using namespace std; typedef long long ll; struct node{ set <int> lazy; }; int a, b, n, di; node t[2][(1 << 18) + 5]; void pushdown(int root, int l, int r){ if(!t[di][root].lazy.empty() && l != r){ for(set <int>::iterator i = t[di][root].lazy.begin() ; i != t[di][root].lazy.end() ; ++i){ int o = *i; t[di][root * 2].lazy.insert(o); t[di][root * 2 + 1].lazy.insert(o); } t[di][root].lazy.clear(); } } void update(int root, int l, int r, int s, int e, int val){ if(l > r || l > e || r < s) return; pushdown(root, l, r); if(l >= s && r <= e){ t[di][root].lazy.insert(val); pushdown(root, l, r); return; } int mid = (l + r) / 2; update(root * 2, l, mid, s, e, val); update(root * 2 + 1, mid + 1, r, s, e, val); } int query(int root, int l, int r, int idx, int val, bool type){ if(l > r || l > idx || r < idx) return 0; pushdown(root, l, r); if(l == r){ int ret = 0; if(type){ ret = *t[di][root].lazy.upper_bound(val); } else{ ret = *(--t[di][root].lazy.upper_bound(val)); } return ret; } int mid = (l + r) / 2; if(idx <= mid) return query(root * 2, l, mid, idx, val, type); return query(root * 2 + 1, mid + 1, r, idx, val, type); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> a >> b; update(1, 1, a, 1, a, 0); update(1, 1, a, 1, a, b); di = 1; update(1, 1, b, 1, b, 0); update(1, 1, b, 1, b, a); //cout << 1 << endl; cin >> n; for(int i = 0 ; i < n ; ++i){ int x, y, type; cin >> x >> y >> type; if(type == 1){ di = 1; int l = query(1, 1, b, y, x, 0); int r = query(1, 1, b, y, x, 1); di = 0; int dolje = query(1, 1, a, x, y, 0); int gore = query(1, 1, a, x, y, 1); ll p1 = (ll)(gore - y) * (ll)(r - l); ll p2 = (ll)(y - dolje) * (ll)(r - l); if(p1 > p2){ swap(p1, p2); } cout << p1 << ' ' << p2 << endl; update(1, 1, a, l, r, y); } else{ di = 0; int dolje = query(1, 1, a, x, y, 0); int gore = query(1, 1, a, x, y, 1); di = 1; int l = query(1, 1, b, y, x, 0); int r = query(1, 1, b, y, x, 1); ll p1 = (ll)(r - x) * (ll)(gore - dolje); ll p2 = (ll)(x - l) * (ll)(gore - dolje); if(p1 > p2){ swap(p1, p2); } cout << p1 << ' ' << p2 << endl; update(1, 1, b, dolje, gore, x); } } return 0; }
#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...