Submission #1156404

#TimeUsernameProblemLanguageResultExecution timeMemory
1156404EsgeerWall (IOI14_wall)C++17
0 / 100
79 ms8260 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; #ifndef Local #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #endif //#define int long long #define ll long long #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define vpi vector<pii> #define vvpi vector<vpi> #define vb vector<bool> #define vvb vector<vb> #define endl '\n' #define sp <<' '<< #define F(i, s, n) for(int i = s; i < (int) n; i++) #define pb push_back #define fi first #define se second const int N = 1e5+5; const int inf = 1e7; struct Update { int mn, mx; }; Update lazy[N*4]; int a[N]; Update merge(Update nw, Update old) { Update merged; merged.mn = min(max(old.mn, nw.mn), nw.mx); merged.mx = max(min(old.mx, nw.mx), nw.mn); return merged; } void push_down(int node, int l, int r) { if(lazy[node].mn == 0 && lazy[node].mx == inf) return; if(l == r) { //cout << "I am here" sp l sp lazy[node].mn << endl; a[l] = lazy[node].mn; return; } lazy[node*2+1] = merge(lazy[node], lazy[node*2+1]); lazy[node*2+2] = merge(lazy[node], lazy[node*2+2]); lazy[node] = {0, inf}; } void update(int node, int l, int r, int L, int R, int mn, int mx) { push_down(node, l, r); if(l > R || r < L) return; if(l >= L && r <= R) { //cout << "UPD" sp l sp r sp mn sp mx <<endl; lazy[node] = {mn, mx}; return; } int m = (l + r) >> 1; update(node*2+1, l, m, L, R, mn, mx); update(node*2+2, m+1, r, L, R, mn, mx); } void finalize(int node, int l, int r) { push_down(node, l, r); if(l != r) { int m = (l + r) >> 1; finalize(node*2+1, l, m); finalize(node*2+2, m+1, r); } } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ F(i, 0, n*4) lazy[i] = {0, inf}; F(i, 0, k) { if(op[i] == 1) { update(0, 0, n-1, left[i], right[i], height[i], inf); } else { update(0, 0, n-1, left[i], right[i], 0, height[i]); } } finalize(0, 0, n-1); F(i, 0, n) finalHeight[i] = a[i]; 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...