Submission #1235900

#TimeUsernameProblemLanguageResultExecution timeMemory
1235900MasterDebater벽 (IOI14_wall)C++20
0 / 100
437 ms106760 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define piii pair<int,pii> #define F first #define S second.first #define T second.second const int N=2e6+10,off=(1<<21); const piii stan={-1,{0,1e9+10}}; piii tour[4*off+5]; pii ans[N]; piii Merge(piii m1,piii m2){ if(m1.F>m2.F)swap(m1,m2); if(m2.T<m1.S)return {m2.F,{m2.T,m2.T}}; if(m2.S>m1.T)return {m2.F,{m2.S,m2.S}}; return {m2.F,{max(m1.S,m2.S),min(m1.T,m2.T)}}; } void update(int x,int y,int l,int r,int node,piii val){ if(r<x or l>y)return; if(x<=l and r<=y){ tour[node]=Merge(tour[node],val); return; } tour[node*2]=Merge(tour[node*2],tour[node]); tour[node*2+1]=Merge(tour[node*2+1],tour[node]); update(x,y,l,(l+r)/2,node*2,val); update(x,y,(l+r)/2+1,r,node*2+1,val); return; } void query(int x,int y,int l,int r,int node){ if(l>y)return; if(l==r){ ans[l]={tour[node].S,tour[node].T}; return; } tour[node*2]=Merge(tour[node*2],tour[node]); tour[node*2+1]=Merge(tour[node*2+1],tour[node]); tour[node]=stan; query(x,y,l,(l+r)/2,node*2); query(x,y,(l+r)/2+1,r,node*2+1); return; } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ for(int i=0;i<4*off+5;i++)tour[i]=stan; for(int i=0;i<k;i++){ if(op[i]==1)update(left[i],right[i],0,off-1,1,{i+1,{height[i],1e9+10}}); else update(left[i],right[i],0,off-1,1,{i+1,{0,height[i]}}); } query(0,n-1,0,off-1,1); for(int i=0;i<n;i++){ finalHeight[i]=max(finalHeight[i],ans[i].first); finalHeight[i]=min(finalHeight[i],ans[i].second); } 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...