| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 742511 | Cookie | Wall (IOI14_wall) | C++14 | 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>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e6 + 5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
//#include "wall.h"
int mx[4 * mxn + 1], mn[4 * mxn + 1];
void push(int nd){
mn[nd << 1] = min(mn[nd << 1], mn[nd]); mx[nd << 1] = min(mn[nd << 1], mx[nd << 1]);
mx[nd << 1] = max(mx[nd], mx[nd << 1]); mn[nd << 1] = max(mn[nd << 1], mx[nd << 1]);
mn[nd << 1 | 1] = min(mn[nd << 1 | 1], mn[nd]); mx[nd << 1 | 1] = min(mn[nd << 1 | 1], mx[nd << 1 | 1]);
mx[nd << 1 | 1] = max(mx[nd], mx[nd << 1 | 1]); mn[nd << 1 | 1] = max(mx[nd << 1 | 1], mn[nd << 1 | 1]);
}
void add(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
mx[nd] = max(mx[nd], v); mn[nd] = max(v, mx[nd]);
return;
}
int mid = (l + r) >> 1;
push(nd);
add(nd << 1, l, mid, ql, qr, v);
add(nd << 1 | 1, mid + 1, r, ql, qr, v);
}
void rem(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
mn[nd] = min(mn[nd], v); mx[nd] = min(mx[nd], v);
return;
}
int mid = (l + r) >> 1;
push(nd);
rem(nd << 1, l, mid, ql, qr, v);
rem(nd << 1 | 1, mid + 1, r, ql, qr, v);
}
int get(int nd, int l, int r, int id){
if(l == r){
return(min(mn[nd], mx[nd]));
}
push(nd);
int mid = (l + r) >> 1;
if(id <= mid){
return(get(nd << 1, l, mid, id));
}else{
return(get(nd << 1 | 1, mid + 1, r, id));
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 1; i <= 4 * n; i++){
mx[i] = 0; mn[i] = 1e9 + 1;
}
forr(i, 0, k){
if(op[i] == 1)add(1, 0, n - 1, left[i], right[i], height[i]);
else rem(1, 0, n - 1, left[i], right[i], height[i]);
}
forr(i, 0, n){
finalHeight[i] = get(1, 0, n - 1, i);
}
return;
}
int main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}