Submission #974386

#TimeUsernameProblemLanguageResultExecution timeMemory
974386hariaakas646Wall (IOI14_wall)C++14
24 / 100
1977 ms73308 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; template <class T> struct SegTree { int size = 1, n; vector<T> segtree; vector<T> vec; T def; // Assign a value void init(int l, T defv) { n = l; def = defv; while (size < n) size *= 2; segtree.assign(2 * size, def); vec.assign(size, def); } T operation(T x, T y) { T out; if(x.f > y.f && x.f <= y.s) { out.f = x.f; } else { out.f = y.f; } if(x.s < y.s && x.s >= y.f) { out.s = x.s; } else { out.s = y.s; } return out; } void recalculate(int x) { segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]); } void build(int x, int l, int r) { if (l == r) { segtree[x] = vec[l]; return; } int mid = (l + r) / 2; build(2 * x + 1, l, mid); build(2 * x + 2, mid + 1, r); recalculate(x); } void build() { build(0, 0, size - 1); } void set(int id, T val) { vec[id] = val; } void update(int x, int l, int r, int id, T val) { if (l == r) { segtree[x] = val; return; } int mid = (l + r) / 2; if (id <= mid) { update(2 * x + 1, l, mid, id, val); } else { update(2 * x + 2, mid + 1, r, id, val); } recalculate(x); } void update(int id, T val) { update(0, 0, size - 1, id, val); } T query(int x, int l, int r, int lx, int rx) { if (lx > r || rx < l) { return def; } if (lx <= l && r <= rx) { return segtree[x]; } int mid = (l + r) / 2; T v1 = query(2 * x + 1, l, mid, lx, rx); T v2 = query(2 * x + 2, mid + 1, r, lx, rx); return operation(v1, v2); } T query(int lx, int rx) { return query(0, 0, size - 1, lx, rx); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ set<pii> st; frange(i, k) { st.insert(mp(left[i], i)); } SegTree<pii> seg; seg.init(k, mp(-1, 1e9)); seg.build(); seti add, rem; set<pii> act; frange(i, n) { while(st.size() && (*st.begin()).f == i) { int id = (*st.begin()).s; st.erase(st.begin()); if(op[id] == 1) { add.insert(id); seg.update(id, mp(height[id], 1e9)); } else { rem.insert(id); seg.update(id, mp(-1, height[id])); } act.insert(mp(right[id]+1, id)); } while(act.size() && (*act.begin()).f == i) { int id = (*act.begin()).s; act.erase(act.begin()); if(op[id] == 1) { add.erase(id); seg.update(id, mp(-1, 1e9)); } else { rem.erase(id); seg.update(id, mp(-1, 1e9)); } } int ai=-1, ri=-1; if(add.size()) ai = *prev(add.end()); if(rem.size()) ri = *prev(rem.end()); if(ai == -1) { finalHeight[i] = 0; } else if(ai > ri) { finalHeight[i] = seg.query(0, k-1).f; } else { finalHeight[i] = seg.query(0, k-1).s; } } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...