제출 #287077

#제출 시각아이디문제언어결과실행 시간메모리
287077theStaticMind벽 (IOI14_wall)C++14
100 / 100
1106 ms69624 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 using namespace std; #include "wall.h" const int S = (1 << (int)ceil(log2(2e6))); vector<int> L(S*2, 0); vector<int> R(S*2, INT_MAX); void push(int j){ if(j < S){ if(L[j] == R[j]){ L[j*2] = R[j*2] = L[j*2+1] = R[j*2+1] = L[j]; } else{ if(L[j*2] == R[j*2]){ if(R[j] < L[j*2]) L[j*2] = R[j*2] = R[j]; if(L[j] > L[j*2]) L[j*2] = R[j*2] = L[j]; } else if(R[j] < L[j*2]){ L[j*2] = R[j*2] = R[j]; } else if(L[j] > R[j*2]){ L[j*2] = R[j*2] = L[j]; } else{ R[j*2] = min(R[j*2], R[j]); L[j*2] = max(L[j*2], L[j]); } if(L[j*2+1] == R[j*2+1]){ if(R[j] < L[j*2+1]) L[j*2+1] = R[j*2+1] = R[j]; if(L[j] > L[j*2+1]) L[j*2+1] = R[j*2+1] = L[j]; } else if(R[j] < L[j*2+1]){ L[j*2+1] = R[j*2+1] = R[j]; } else if(L[j] > R[j*2+1]){ L[j*2+1] = R[j*2+1] = L[j]; } else{ R[j*2+1] = min(R[j*2+1], R[j]); L[j*2+1] = max(L[j*2+1], L[j]); } } L[j] = 0, R[j] = INT_MAX; } } void rangeupdate(int j, int x, int y, int l, int r, int t, int v){ if(y < l || r < x) return; push(j); if(l <= x && y <= r){ if(t == 1){ L[j] = max(L[j], v); R[j] = max(R[j], v); } else{ L[j] = min(L[j], v); R[j] = min(R[j], v); } return; } rangeupdate(j*2,x,(x+y)/2,l,r,t,v); rangeupdate(j*2+1,(x+y)/2+1,y,l,r,t,v); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ for(int i = 0; i < k; i++){ rangeupdate(1,0,S-1,left[i],right[i],op[i], height[i]); } for(int i = 1; i < S; i++) push(i); for(int i = 0; i < n; i++){ finalHeight[i] = L[S + 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...