제출 #538598

#제출 시각아이디문제언어결과실행 시간메모리
538598Cantfindme벽 (IOI14_wall)C++17
61 / 100
686 ms262144 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; // #define int long long typedef long long ll; typedef pair<int,int> pi; #define f first #define s second #define FAST ios_base::sync_with_stdio(0); cin.tie(0); #define all(x) x.begin(),x.end() const ll maxn = 4000010; const ll INF = INT_MAX/4; const int mod = 1e9+7; ll ans[maxn]; struct node { int s, m, e; ll maxv= INF, minv=0; node *l, *r; node (int _s, int _e) { s = _s; e = _e; m = (s+e)/2; if (s != e) { l = new node(s,m); r = new node(m+1,e); } } void calc(int type, ll x) { if (type == 0) { //minimise maxv = min(maxv, x); minv = min(minv, x); } else { minv = max(minv, x); maxv = max(maxv, x); } } void push() { assert(s != e); if (minv != 0) { l -> setmin(s, m, minv); r -> setmin(m+1, e, minv); minv = 0; } if (maxv != INF) { l -> setmax(s, m, maxv); r -> setmax(m+1, e, maxv); maxv = INF; } } void setmax(int x, int y, ll nv) { if (s == x and e == y) { calc(0, nv); } else { push(); if (x > m) r -> setmax(x,y, nv); else if (y <= m) l -> setmax(x,y,nv); else l -> setmax(x,m,nv), r -> setmax(m+1,y,nv); } } void setmin(int x, int y, ll nv) { if (s == x and e == y) { calc(1, nv); } else { push(); if (x > m) r -> setmin(x,y, nv); else if (y <= m) l -> setmin(x,y,nv); else l -> setmin(x,m,nv), r -> setmin(m+1,y,nv); } } void rmq() { // cout << s << " " << e << " " << minv << " " << maxv << "\n"; if (s == e) ans[s] = minv; else { push(); l -> rmq(); r -> rmq(); } } }*root; void buildWall(int n, int Q, int op[], int left[], int right[], int height[], int finalHeight[]){ root = new node(0,n); for (int q = 0; q < Q; q++) { int t = op[q]; int l = left[q]; int r = right[q]; int h = height[q]; if (t == 1) { //adding -> set min root -> setmin(l,r,h); } else { root -> setmax(l,r,h); } // root -> rmq(); // for (int i = 0; i< n;i++) cout <<ans[i] << " "; // cout << "\n"; } root -> rmq(); for (int i =0;i<n;i++) { finalHeight[i] = ans[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...