| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 395142 | jeroenodb | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <bitset>
#include <cassert>
#include <algorithm>
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
const int mxN = 1e5+1;
struct segtree {
int n, ptwo;
struct Node {
// Change here the values you want to propagate, and store
int mn =0, mx = 100000;
int l,r;
Node () {}
Node(int i) {
l = r = i;
}
};
vector<Node> d;
void set(int i, int mn, int mx) {
Node& rc = d[i];
rc.mn = max(mn,rc.mn);
rc.mx = min(mx,rc.mx);
if(rc.mn>rc.mx) {
if(mn>rc.mx) rc.mx = rc.mn;
else rc.mn = rc.mx;
}
}
void push(int i) {
// Pushes the propagation values down to the children
set(2*i, d[i].mn, d[i].mx);
set(2*i+1, d[i].mn, d[i].mx);
d[i].mn = 0; d[i].mx = 100000;
}
segtree(int _n) {
n = _n;
ptwo= 1;
while(ptwo<n) ptwo*=2;
d.resize(2*ptwo);
for(int i=ptwo;i<ptwo*2;++i) {
d[i] = Node(i-ptwo);
}
for(int i=ptwo-1;i>0;--i) {
d[i].l = d[i*2].l; d[i].r = d[i*2+1].r;
}
}
void query(int i=1, int mn = 0, int mx = 100000) {
Node& c = d[i];
if(c.l>=n) return;
mn = max(mn,c.mn);
mx = min(mx,c.mx);
if(mn>mx) {
if(c.mn>mx) mn = mx;
else mx = mn;
}
if(c.l==c.r) {
cout << mn << '\n';
return;
}
query(i*2,mn,mx);
query(i*2+1,mn,mx);
}
void update(int l, int r, bool lower, int val, int i=1) {
Node& c = d[i];
if(c.l < l or r < c.r ) {
push(i);
int mid = (c.r+c.l)/2;
if(l<=mid) {
update(l,r,lower,val,i*2);
}
if(r>mid) {
update(l,r,lower,val,i*2+1);
}
} else {
if(!lower) {
c.mn = max(val,c.mn);
if(c.mn>c.mx) c.mx = c.mn;
} else {
c.mx = min(val,c.mx);
if(c.mn>c.mx) c.mn = c.mx;
}
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k; cin >> n >> k;
segtree segt(n);
while(k--) {
int t,l,r,h; cin >> t >> l >> r >> h;
segt.update(l,r,t-1,h);
}
segt.query();
}