Submission #1062947

#TimeUsernameProblemLanguageResultExecution timeMemory
1062947andrei_iorgulescuWall (IOI14_wall)C++14
100 / 100
2466 ms161908 KiB
#include <bits/stdc++.h> #include "wall.h" #warning That's not FB, that's my FB using namespace std; struct node { int mx = 0, mx2 = -1, mn = 0, mn2 = -1; }; vector<node> aint; void prop(int nod, int l, int r) { if (l == r) return; aint[2 * nod].mx = min(aint[2 * nod].mx, aint[nod].mx); aint[2 * nod].mn = min(aint[2 * nod].mn, aint[nod].mx); aint[2 * nod].mx = max(aint[2 * nod].mx, aint[nod].mn); aint[2 * nod].mn = max(aint[2 * nod].mn, aint[nod].mn); aint[2 * nod + 1].mx = min(aint[2 * nod + 1].mx, aint[nod].mx); aint[2 * nod + 1].mn = min(aint[2 * nod + 1].mn, aint[nod].mx); aint[2 * nod + 1].mx = max(aint[2 * nod + 1].mx, aint[nod].mn); aint[2 * nod + 1].mn = max(aint[2 * nod + 1].mn, aint[nod].mn); if (aint[2 * nod].mn == aint[2 * nod].mx) aint[2 * nod].mx2 = aint[2 * nod].mn2 = -1; else { aint[2 * nod].mx2 = max(aint[2 * nod].mx2, aint[nod].mn); aint[2 * nod].mn2 = min(aint[2 * nod].mn2, aint[nod].mx); } if (aint[2 * nod + 1].mn == aint[2 * nod + 1].mx) aint[2 * nod + 1].mx2 = aint[2 * nod + 1].mn2 = -1; else { aint[2 * nod + 1].mx2 = max(aint[2 * nod + 1].mx2, aint[nod].mn); aint[2 * nod + 1].mn2 = min(aint[2 * nod + 1].mn2, aint[nod].mx); } } void update(int nod, int l, int r, int st, int dr, int tip, int h) { if (r < st or dr < l) return; prop(nod,l,r); if (st <= l and r <= dr) { if (tip == 1) { if (h <= aint[nod].mn) return; if (aint[nod].mn2 == -1 or h < aint[nod].mn2) { if (aint[nod].mx2 == aint[nod].mn) aint[nod].mx2 = h; //aint[nod].lazy_tag_min = true; aint[nod].mn = h; if (aint[nod].mn2 == -1) { //aint[nod].lazy_tag_max = true; aint[nod].mx = h; } //cout << "wow" << nod << ' ' << l << ' ' << r << endl; return; } } else { if (h >= aint[nod].mx) return; if (aint[nod].mx2 == -1 or h > aint[nod].mx2) { if (aint[nod].mn2 == aint[nod].mx) aint[nod].mn2 = h; //aint[nod].lazy_tag_max = true; aint[nod].mx = h; if (aint[nod].mx2 == -1) { //aint[nod].lazy_tag_min = true; aint[nod].mn = h; } return; } } } //cout << nod << ' ' << l << ' ' << r << endl; int mij = (l + r) / 2; update(2 * nod, l, mij, st, dr, tip, h); update(2 * nod + 1, mij + 1, r, st, dr, tip, h); vector<int> ele = {aint[2 * nod].mx, aint[2 * nod].mx2, aint[2 * nod].mn, aint[2 * nod].mn2, aint[2 * nod + 1].mx, aint[2 * nod + 1].mx2, aint[2 * nod + 1].mn, aint[2 * nod + 1].mn2}; sort(ele.begin(),ele.end()); vector<int> e2; for (int i = 0; i < 8; i++) if ((i == 0 or ele[i] != ele[i - 1]) and ele[i] != -1) e2.push_back(ele[i]); if (e2.size() == 1) { aint[nod].mx = aint[nod].mn = e2[0]; aint[nod].mx2 = aint[nod].mn2 = -1; } else { int sz = e2.size(); aint[nod].mx = e2[sz - 1]; aint[nod].mx2 = e2[sz - 2]; aint[nod].mn = e2[0]; aint[nod].mn2 = e2[1]; } } int query(int nod, int l, int r, int st, int dr) { if (r < st or dr < l) return 0; prop(nod,l,r); if (st <= l and r <= dr) return aint[nod].mn; int mij = (l + r) / 2; return max(query(2 * nod,l,mij,st,dr), query(2 * nod + 1,mij + 1,r,st,dr)); } void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { aint.resize(4 * n + 5); for (int i = 0; i < k; i++) { left[i]++; right[i]++; update(1,1,n,left[i],right[i],op[i],height[i]); } for (int i = 0; i < n; i++) finalHeight[i] = query(1,1,n,i + 1,i + 1); } ///hai sa vedem daca iese si cu beats :)

Compilation message (stderr)

wall.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...