Submission #1207285

#TimeUsernameProblemLanguageResultExecution timeMemory
1207285simplemind_31Wall (IOI14_wall)C++20
0 / 100
76 ms8076 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; int N,tiempo=-1e9; vector<pair<int,int>> segmentres; vector<pair<int,int>> lazy[2]; // valor,tiempo void propagate(int node,int l,int r){ if(lazy[0][node].first!=-1 && lazy[1][node].first!=-1 && lazy[0][node].first>lazy[1][node].first){ if(lazy[0][node].second<lazy[1][node].second){ lazy[0][node].first=lazy[1][node].first; }else{ lazy[1][node].first=lazy[0][node].first; } } if(l==r){ if(lazy[0][node].first!=-1){ segmentres[node].second=lazy[0][node].first; } if(lazy[1][node].first!=-1){ segmentres[node].first=lazy[1][node].first; } return; } int hiji=2*node+1,hijd=2*node+2; if(lazy[0][node].first!=-1){ segmentres[node].second=lazy[0][node].first; lazy[0][hiji].first=max(lazy[0][hiji].first,lazy[0][node].first); lazy[0][hijd].first=max(lazy[0][hijd].first,lazy[0][node].first); lazy[0][hiji].second=tiempo++; lazy[0][hijd].second=tiempo++; } if(lazy[1][node].first!=-1){ segmentres[node].first=lazy[1][node].first; lazy[1][hiji].first=min(lazy[1][hiji].first,lazy[1][node].first); lazy[1][hijd].first=min(lazy[1][hijd].first,lazy[1][node].first); lazy[1][hiji].second=tiempo++; lazy[1][hijd].second=tiempo++; } lazy[0][node].first=lazy[1][node].first=-1; } pair<int,int> query(int node,int l,int r,int i,int j){ propagate(node,l,r); if(j<l || r<i){ return {-1e9,1e9}; } if(i<=l && r<=j){ return segmentres[node]; } int hiji=2*node+1,hijd=2*node+2,mid=(l+r)>>1; pair<int,int> fir=query(hiji,l,mid,i,j),sec=query(hijd,mid+1,r,i,j); return {max(fir.first,sec.first),min(fir.second,sec.second)}; } void update(int node,int l,int r,int i,int j,int val,int tipo){ propagate(node,l,r); int mid=(l+r)>>1,hiji=2*node+1,hijd=2*node+2; if(i==l && j==r){ pair<int,int> ans=query(node,l,r,i,j); if(tipo==1){ if(ans.first<=val){ lazy[0][node].first=val; lazy[0][node].second=tiempo++; } }else{ if(ans.second>=val){ lazy[1][node].first=val; lazy[1][node].second=tiempo++; } } return; } if(i<=mid){ update(hiji,l,mid,i,mid,val,tipo); } if(j>mid){ update(hijd,mid+1,r,mid+1,j,val,tipo); } segmentres[node].first=max(segmentres[hiji].first,segmentres[hijd].first); segmentres[node].second=min(segmentres[hiji].second,segmentres[hijd].second); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ for(int i=0;i<n;i++){ finalHeight[i]=0; } for(int i=0;i<k;i++){ for(int j=left[i];j<=right[i];j++){ if(op[i]==1){ finalHeight[j]=max(finalHeight[j],height[j]); }else{ finalHeight[j]=min(finalHeight[j],height[j]); } } } 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...