Submission #555058

#TimeUsernameProblemLanguageResultExecution timeMemory
555058AriaHWall (IOI14_wall)C++17
100 / 100
711 ms75596 KiB
#include "wall.h" #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); #define mashtali return cout << "Hello, World!", 0; const int N = 2e6 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(time(nullptr)); int n, k, Mn[N << 2], Mx[N << 2], lz[N << 2]; void S(int v, int tl, int tr) { if(lz[v] == -1 || tl == tr) return; Mn[v << 1] = Mx[v << 1] = Mn[v << 1 | 1] = Mx[v << 1 | 1] = lz[v << 1] = lz[v << 1 | 1] = lz[v]; lz[v] = -1; } void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1) /// baraye min { S(v, tl, tr); if(l > tr || r < tl || Mx[v] <= x) return; if(l <= tl && tr <= r && Mn[v] == Mx[v]) { Mx[v] = Mn[v] = lz[v] = x; return; } int mid = (tl + tr) >> 1; upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr); Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]); Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]); } void UPD(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1) { S(v, tl, tr); if(l > tr || r < tl || Mn[v] >= x) return; if(l <= tl && tr <= r && Mx[v] == Mn[v]) { Mn[v] = Mx[v] = lz[v] = x; return; } int mid = (tl + tr) >> 1; UPD(l, r, x, v << 1, tl, mid), UPD(l, r, x, v << 1 | 1, mid + 1, tr); Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]); Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]); } int get(int p, int v = 1, int tl = 0, int tr = n - 1) { S(v, tl, tr); if(tl == tr) return Mx[v]; int mid = (tl + tr) >> 1; if(p <= mid) return get(p, v << 1, tl, mid); else return get(p, v << 1 | 1, mid + 1, tr); } void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[]) { n = _n; k = _k; for(int i = 0; i < k; i ++) { if(op[i] == 1) { UPD(left[i], right[i], height[i]); } else { upd(left[i], right[i], height[i]); } } for(int i = 0; i < n; i ++) { finalHeight[i] = get(i); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...