Submission #1017645

#TimeUsernameProblemLanguageResultExecution timeMemory
1017645dostsWall (IOI14_wall)C++17
0 / 100
314 ms8128 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(xx) xx.begin(),xx.end() pii propmini(pii state,int minimise) { if (minimise == -1) return state; if (state.ss != -1) { if (state.ss <= minimise) return state; } if (state.ff < minimise) return {state.ff,minimise}; return {minimise,minimise}; } pii propmaxi(pii state,int maximise) { if (maximise == -1) return state; if (state.ff == -1) { if (state.ss <= maximise) return {maximise,maximise}; return {maximise,state.ss}; } if (state.ss == -1) { if (state.ff >= maximise) return state; return {maximise,state.ss}; } if (maximise < state.ff) return state; if (maximise > state.ss) return {maximise,maximise}; return {maximise,state.ss}; } struct ST { vector<pii> lazy; vector<pii> t; ST(int nn) { lazy.assign(4*nn+1,pii{-1,-1}); t.assign(4*nn+1,pii{-1,-1}); } void push(int node,bool leaf) { t[node] = propmaxi(t[node],lazy[node].ff); t[node] = propmini(t[node],lazy[node].ss); if (!leaf) { lazy[2*node] = propmaxi(lazy[2*node],lazy[node].ff); lazy[2*node] = propmini(lazy[2*node],lazy[node].ss); lazy[2*node+1] = propmaxi(lazy[2*node+1],lazy[node].ff); lazy[2*node+1] = propmini(lazy[2*node+1],lazy[node].ss); } lazy[node] = {-1,-1}; } void mini(int node,int l,int r,int L,int R,int v) { push(node,l==r); if (l > R || r < L) return; if (l >= L && r <= R) { lazy[node] = propmini(lazy[node],v); push(node,l==r); return; } int m = (l+r) >> 1; mini(2*node,l,m,L,R,v); mini(2*node+1,m+1,r,L,R,v); } void maxi(int node,int l,int r,int L,int R,int v) { push(node,l==r); if (l > R || r < L) return; if (l >= L && r <= R) { lazy[node] = propmaxi(lazy[node],v); push(node,l==r); return; } int m = (l+r) >> 1; maxi(2*node,l,m,L,R,v); maxi(2*node+1,m+1,r,L,R,v); } pii query(int node,int l,int r,int p) { push(node,l==r); if (l == r) return t[node]; int m = (l+r) >> 1; if (p<=m) return query(2*node,l,m,p); return query(2*node+1,m+1,r,p); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ ST st(n); for (int i=0;i<k;i++){ if (op[i] == 1) { //ADD st.maxi(1,1,n,left[i]+1,right[i]+1,height[i]); } else { //REM st.mini(1,1,n,left[i]+1,right[i]+1,height[i]); } } for (int i=0;i<n;i++) finalHeight[i] = max(0,st.query(1,1,n,i+1).first); 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...