| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 59213 | Bruteforceman | Wall (IOI14_wall) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n;
const int inf = 1e8;
class info {
public:
int mn, mx;
info () {}
info (int mn, int mx) : mn (mn), mx (mx) {}
};
info t[2000010 * 4];
info p[2000010 * 4];
bool vis[2000010 * 4];
info addMin(info i, int mn) {
if(mn <= i.mn) return info (mn, mn);
else if (mn <= i.mx) return info (i.mn, mn);
else return i;
}
info addMax(info i, int mx) {
if(i.mx <= mx) return info (mx, mx);
else if (i.mn <= mx) return info (mx, i.mx);
else return i;
}
info putMin(info i, int mn) {
if(mn <= i.mx) return info (mn, mn);
else if (mn <= i.mn) return info (mn, i.mx);
else return i;
}
info putMax(info i, int mx) {
if(i.mn <= mx) return info (mx, mx);
else if (i.mx <= mx) return info (i.mn, mx);
else return i;
}
void propagate(int c) {
if(vis[c] == false) return ;
int l = c << 1;
int r = l + 1;
p[l] = putMax(p[l], p[c].mx);
p[l] = putMin(p[l], p[c].mn);
t[l] = addMax(t[l], p[c].mx);
t[l] = addMin(t[l], p[c].mn);
p[r] = putMax(p[r], p[c].mx);
p[r] = putMin(p[r], p[c].mn);
t[r] = addMax(t[r], p[c].mx);
t[r] = addMin(t[r], p[c].mn);
vis[l] = vis[r] = true;
vis[c] = false;
p[c] = info(inf, 0);
}
void updMax (int x, int y, int val, int c = 1, int b = 1, int e = n) {
if(x <= b and e <= y) {
vis[c] = true;
p[c] = putMax(p[c], val);
t[c] = addMax(t[c], val);
return ;
}
if(y < b or e < x) return ;
propagate(c);
int l = c << 1;
int r = l + 1;
int m = (b + e) >> 1;
updMax(x, y, val, l, b, m);
updMax(x, y, val, r, m+1, e);
t[c].mx = max(t[l].mx, t[r].mx);
t[c].mn = min(t[l].mn, t[r].mn);
}
void updMin (int x, int y, int val, int c = 1, int b = 1, int e = n) {
if (x <= b and e <= y) {
vis[c] = true;
p[c] = putMin(p[c], val);
t[c] = addMin(t[c], val);
return ;
}
if(y < b or e < x) return ;
propagate(c);
int l = c << 1;
int r = l + 1;
int m = (b + e) >> 1;
updMin(x, y, val, l, b, m);
updMin(x, y, val, r, m+1, e);
t[c].mx = max(t[l].mx, t[r].mx);
t[c].mn = min(t[l].mn, t[r].mn);
}
int getIndice(int x, int c = 1, int b = 1, int e = n) {
if(b == e) {
return t[c].mx;
}
propagate(c);
int l = c << 1;
int r = l + 1;
int m = (b + e) >> 1;
if(x <= m) return getIndice(x, l, b, m);
else return getIndice(x, r, m+1, e);
}
void build(int c = 1, int b = 1, int e = n) {
t[c] = info (0, 0);
p[c] = info (inf, 0);
vis[c] = false;
if(b == e) return ;
int l = c << 1;
int r = l + 1;
int m = (b + e) >> 1;
build(l, b, m);
build(r, m+1, e);
}
int main(int argc, char const *argv[])
{
int q;
scanf("%d %d", &n, &q);
build ();
for(int i = 1; i <= q; i++) {
int opt, x, y, val;
scanf("%d %d %d %d", &opt, &x, &y, &val);
x++;
y++;
if(opt == 1) {
updMax(x, y, val);
} else {
updMin(x, y, val);
}
}
for(int i = 1; i <= n; i++) {
printf("%d\n", getIndice(i));
}
return 0;
}